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

Question

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

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

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