Поиск непрерывного подмассива (без суммы)

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

// 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;
    }
  }
}

c++ sub-array
person Shreya Kataria    schedule 09.08.2015    source источник
comment
Ваш вариант использования требует вывода O(n^3) значений. Очевидно, вы не сможете сделать это менее чем за O(n^3).   -  person Sneftel    schedule 09.08.2015
comment
(Также обратите внимание, что хотя ваш алгоритм действительно O(n^3), на самом деле он неверен.)   -  person Sneftel    schedule 09.08.2015
comment
Все последовательности, которые вы печатаете, включают A[N-1]. Вы также печатаете одну и ту же последовательность несколько раз. Я не уверен, что эта программа должна демонстрировать.   -  person Igor Tandetnik    schedule 09.08.2015

Ответы (1)


arrow_upward
0
arrow_downward

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

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. либо его конечная точка, либо его длина

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

person Andras Deak    schedule 10.08.2015