Нахождение смежного подмассива (без суммы)

Question

Я хочу попросить БЫСТРЫЕ методы поиска смежных под-массивов для данного массива. Обратите внимание, что я не ищу максимальную сумму смежных подмассивов, скорее хочу выполнить другие операции над полученными подмассивами. Я уже знаю о следующем алгоритме, но ищу более эффективные алгоритмы, так как у этого очень низкая временная сложность.

// N = number of elements in array A.
void subarr(int N, int A[]) {
  for (int i = 0; i < N; i++) {
    for (int j = i; j < N; j++) {
      for (int k = j; k < N; k++) {
        cout << A[k] << ' ';
      }
      cout << endl;
    }
  }
}

Answer 1

Как отмечали другие в комментариях, ваш пример неверен. Должно читаться как то

for (int i = 0; i < N; i++) {
   for (int j = N-1; j >= i; j--) {
      for (int k=i; k<=j; k++) {
         cout << "A[" << k << "] ";
     }
     cout << endl;
   }
}

Обратите внимание, что я изменил вывод, просто печатая буквально A[k], Это будет печатать каждый подмассив ровно один раз.

Что касается вашего вопроса, опять же, как уже отмечали другие, этот алгоритм печатает каждый подмассив один раз, без какой-либо дополнительной работы. Я не верю, что вы можете сэкономить время выполнения, так как это почти наименьшее количество работы, которое вам нужно сделать. У вас есть некоторые накладные расходы из трех вложенных циклов, но вам, вероятно, нужны все три: подмассив определяется, например,

1. его отправная точка
2. либо его конечная точка или его длина

и вы должны напечатать / вырезать то, что находится между ними, создавая третий цикл.