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

2 comments:

  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

    ReplyDelete
  2. They all play excellently on mobile, optimized efficiently for each Android and iOS gadgets. Perhaps the best promotion for normal gamers at Red Dog is what's recognized as|often known as} the 24/7 bonus. But these video games which might be} obtainable are of high quality|of prime of the range|of 1xbet prime quality} and supply an excellent expertise for playing on the go.

    ReplyDelete