Cześć,
Algorytm Kadane pozwala na znalezienie w jakiejś tablicy spójnej podtablicy o największej sumie elementów i zwróceniu tej sumy.
np. przy tablicy takiej int[] tab = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
zwróci sumę ciągu 187
.
Chciałem ten algorytm rozbudować tak, żeby pokazywał też wyraz początkowy i wyraz końcowy tej podtablicy. W powyższym przypadku byłyby to wyrazy o nr 2(59) i 6(97).
Ale coś nie działa. Czy ktoś wie co trzeba zmienić w poniższym kodzie, żeby zaczęło działać poprawnie? Obecnie pokazuje mi p=0 i k=0.
package com.company;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
static int Kadane(int tab[]) {
int sumaMax = tab[0];
int sumaLoc = tab[0];
int size = tab.length;
int p = 0;
int k = 0;
int licznik = 0;
for (int i = 1; i < size; i++) {
sumaLoc = Math.max(tab[i], sumaLoc + tab[i]);
if (tab[i] > (sumaLoc + tab[i])) {
p = i;
k = i;
licznik = 0;
}
if (tab[i] <= (sumaLoc + tab[i])) {
licznik++;
p = i - licznik;
k = i;
}
sumaMax = Math.max(sumaMax, sumaLoc);
if (sumaLoc > sumaMax) {
p = i;
k = i;
licznik = 0;
}
if (sumaLoc <= sumaMax) {
licznik++;
p = i - licznik;
k = i;
}
}
return sumaMax;
}
public static void main (String[]args) throws FileNotFoundException {
int n = 10;
int[] tab = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
int p = 0;
int k = 0;
System.out.println(Kadane(tab));
System.out.println("Początek przedziału to: p = " + p);
System.out.println("Początek przedziału to: k = " + k);
}
}