Нужен более эффективный способ чтения подмассивов

Question

В постановке задачи задается число таких подмассивов, где i

Что я сделал:

Я запустил цикл от i=0 до n-2: и основная логика, которую я использовал, заключалась в том, что если первые два элемента в отсортированном подмассиве больше или равны максимуму, то все пары будут больше любого элемента. и каждый раз, когда я получаю подмассив, я добавляю в него следующий элемент и снова устанавливаю эти три переменные. Пропускаю 15/20 тс другие получаю TLE:
Ограничения:
1<= N <= 10 ^ 5
1<= а <=10^9

for(int i=0;i<n-2;i++)
{
    int r=i+2;
    vector<int> temp(inp.begin()+i,inp.begin()+r+1);
    sort(temp.begin(),temp.end());
    max_elem=temp[1];min_elem=temp[0];
    int maximum=temp[temp.size()-1];


    //cout<<max_elem<<" "<<min_elem<<"\n";

    while(r<n && max_elem+min_elem >= maximum)
    {   
        //cout<<max_elem<<" "<<min_elem<<" "<<inp[r]<<"\n";
        cnt++;
        r++;

        if(inp[r]<min_elem) {max_elem=min_elem;min_elem=inp[r];}
        else if(inp[r]<max_elem) max_elem=inp[r];
        else if(inp[r]>maximum) maximum=inp[r];

    }

}
cout<<cnt<<"\n";

Образец ТС:

I1:
5
7 6 5 3 4
O1:
6
Объяснение:
6 подмассивов удовлетворяют условиям: (7,6,5),(7,6,5,3),(7,6,5,3,4),(6,5,3),(6,5,3), 4), (5,3,4).

I2:
5
1 2 3 5 6
O2:
3
Объяснение:
(1,2,3), (2,3,5), (3,5,6) - (ПРИМЕЧАНИЕ: 1,2,3,5 - это не ответ 1+2 < 5)

Answer 1

Наивный подход к этому заключается в следующем. Ваша логика верна и это то, что я реализовал. Я изменил сортировку (NlogN) за один проход (N), найдя только 2 самых маленьких и самых больших числа. Я не скомпилировал код и не уверен, что он работает как задумано. Он имеет общую сложность (N*N*N).

Время выполнения можно улучшить, выполнив некоторые дополнительные проверки:

• min1 + min2 >= maxусловие может быть проверено после каждого внутреннего (k) цикла, нарушая его, если оно нарушается для одного случая.

• Если условие не выполняется, например, для подмассива 4-7, нет необходимости проверять любую другую подстроку, включая 4-7. Сохраняя случаи нарушения и проверяя их перед каждым циклом, общее время выполнения может быть улучшено.

  int min1;
  int min2;
  int max;
  int count = 0;
  for(int i = 2; i < n; i++){
      for(int j = 0; j < i - 2; j++){
          max = -1;
          min1 = min2 = 1000000000;
          for(int k = j; k <= i; k++){
              if(inp[k] > max)
                  max = inp[k];
              if(inp[k] < min1){
                  min1 = inp[k];
                  continue;
              }
              if(inp[k] < min2){
                  min2 = inp[k];
              }
          }
          if(min1 + min2 >= max)
              count++;
      }
  } 
  

Answer 2

Могут быть некоторые ошибки, но вот общая идея для решения O(n log n):

Мы сохраняем окна элементов от startIdx до endIdx. Если это допустимый подмассив, это означает, что мы можем расширить его, мы можем добавить к нему другой элемент, поэтому мы увеличиваем endIdx. Если он недействителен, он не будет действительным независимо от того, насколько мы его расширим, поэтому нам нужно уменьшить его, увеличив startIdx.

псевдокод:

multiset<int> nums;

int startIdx = 0, endIdx = 0;
int sol = 0;

while(endIdx != inp.size()) {
    if (endIdx - startIdx < 3) {
       nums.add(inp[endIdx]);  
       endIdx++;
    } else  {
       if (nums.lowestElement() + nums.secondLowestElement() < nums.highestElement()) {
          nums.remove(nums.find(inp[startIdx]));
          startIdx++;
       } else { 
            sol += endIdx - startIdx - 2; // amount of valid subarrays ending in inp[endIdx - 1]
            nums.add(inp[endIdx]);  
            endIdx++;
       }
    }
}