Kadane's Algorithm (http://en.wikipedia.org/wiki/Kadane's_Algorithm)

Here the java solution: M[i] = max(A[i], M[i-1] + A[i]) void largestSumSubArray(int[] a){ if (a.length != 0){ int[] m = new int[a.length]; m[0] = a[0]; int maxIndex = m[0]; for (int i = 1; i maxIndex) maxIndex = i; } boolean found = false; int i = maxIndex - 1; while (!found){ if (m[i] > 0) i--; } System.out.printf("%d - %d", i, maxIndex); } }

Assuming the sub array can be any size and only positive integers: you only need to check which of the two end numbers on the array is bigger and then take that the list that includes that number and not the other.