JavaでKadaneのアルゴリズムを次のように実装しています。基本的には、連続する部分配列の最大合計を見つけることです。
String[] numbers = string.split(",");
int max_so_far = 0;
int max_ending_here = 0;
for (int i = 0; i < numbers.length-1;i++){
max_ending_here = max_ending_here + Integer.parseInt(numbers[i]);
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
System.out.println(max_so_far);
ただし、配列に負の数と正の数の組み合わせがある場合、これは機能しません。たとえば、次のようになります。
2,3,-2,-1,10
最大値として 12 を返す必要があります。今のところ5を返します