Chcę poprosić o SZYBKIE metody wyszukiwaniaciągłe pod-tablice dla danej tablicy. Należy pamiętać, że nie szukam maksymalnych sum ciągłych pod-tablic, raczej chcę wykonywać inne operacje na otrzymanych pod-tablicach. Jestem już świadomy następującego algorytmu, ale szukam bardziej wydajnych algorytmów, ponieważ ten ma bardzo niską złożoność czasową.
// 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;
}
}
}
Odpowiedzi:
0 dla odpowiedzi № 1Jak zauważyli inni w komentarzach, twój przykład jest niepoprawny. Powinno to brzmieć jak coś takiego
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;
}
}
Zauważ, że zmieniłem wyjście na drukowanie tylko dosłownie A[k]. Spowoduje to wydrukowanie każdej podtablicy dokładnie raz.
Co do twojego pytania, podobnie jak inniwskazano, że ten algorytm drukuje każdą podtablicę raz, bez dodatkowej pracy. Nie sądzę, abyś mógł zaoszczędzić czas wykonywania, ponieważ jest to prawie najmniej pracy, którą musisz wykonać. Masz trochę narzutu z trzech zagnieżdżonych pętli, ale prawdopodobnie potrzebujesz wszystkich trzech: podtablica jest określona na przykład przez
- jego punkt wyjścia
- punkt końcowy lub długość
i musisz wydrukować / wyciąć to, co jest pomiędzy, dając początek trzeciej pętli.