Tuesday, June 13, 2017

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);


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.

1 comment:

  1. Sands Casino Review – Safe & Secure Online Gaming
    Sands 바카라사이트 Casino review 2021. Casino games on offer with high-quality games for players from all over septcasino the 메리트카지노 world. Read our casino review before