Largest Sum in Contiguous Array

Kadane's Algorithm

if we know the maximum sub-array sum ending at position i, what is the maximum sub-array sum ending at position i + 1 ? The answer turns out to be relatively straightforward: either the maximum sub-array sum ending at position i + 1 includes the maximum sub-array sum ending at position i as a prefix, or it doesn't. Thus, we can compute the maximum sub-array sum ending at position i for all positions i by iterating once over the array. As we go, we simply keep track of the maximum sum we've ever seen. Thus, the problem can be solved with the following code, expressed here in Java:

public class MaximumSubarray {

public static void main(String[] args) {
int arr[] = { -2, -1, -3, -4, -1, -2, -1, -5, -4 };

int max_end, max_so_far;
max_end = max_so_far = arr[0];
for (int i : arr) {
max_end = max(i, max_end + i);
max_so_far = max(max_so_far, max_end);
}
System.out.println(max_end);
System.out.println(max_so_far);

}

private static int max(int i, int j) {
    return i > j ? i : j;
 }
}

Note: This will also work for all negative numbers where the result will be least negative number.