cześć, poszukuję wydajniejszego sposobu na znalezienie najwiekszego podzbioru z tablicy.
tablica = [0, 1, 5, -3, 7, 3, 9, -2, 1]
Czyli chce znalezc fragment tablicy, ktory po zsumowaniu będzie miał największą wartość.
Stworzyłem algorytm(pętle kwadratowa)
for (int i=1; i<n; i++)
for (int j=i+1; j<n; j++){
l = tab[j] - tab[i-1];
if (l>liczbanaj)
liczbanaj=l;
dla n = liczebnosc tablicy + 1
Czy jest wydajniejszy i szybszy sposob>
0
1
Jeśli pytasz o podciąg spójny, to tak jak powyżej @lion137 Ci powiedział. Ale jak faktycznie miałeś na myśli podzbiór, jak napisałeś — to po prostu będzie to podzbiór wszystkich dodatnich/nieujemnych (na jedno wychodzi, bo zera nie zmieniają sumy) elementów.
A jak miałeś na myśli największy podzbiór k-elementowy, to to będzie największe k elementów.