Java implementation of Kadane’s Algorithm(solution to Maximum Subarray Problem).
a = { -2, 1, -3, 4, -1, 2, 1, -5, 4 } OUT: Sum: 6 start: 3 end: 6
// ? 2019 TheFlyingKeyboard and released under MIT License // theflyingkeyboard.net public class Main { public static void main(String[] args) { int[] a = { -2, 1, -3, 4, -1, 2, 1, -5, 4 }; int maxEndingHere = a[0]; int startIndex = 0; int startIndexOld = 0; int endIndex = 0; int maxSoFar = 0; for(int i = 0; i < a.length; ++i){ maxEndingHere = max(a[i], maxEndingHere + a[i]); maxSoFar = max(maxSoFar, maxEndingHere); if(maxEndingHere < 0){ startIndex = i + 1; }else if(maxEndingHere == maxSoFar){ startIndexOld = startIndex; endIndex = i; } } System.out.println("Sum: " + maxSoFar + " start: " + startIndexOld + " end: " + endIndex); } private static int max(int a, int b){ return a > b ? a : b; } }