Tuesday, September 4, 2012

Max sum in an array

Given an array of integers A find a, b such that \sum_{i=a}^b A[i] is maximized
Pubblicato da a

1 comment:

  1. Claudio CorsiSeptember 7, 2012 at 7:53 AM

    int[] A = new int[] {-1, -1, 3, 2, -1, 5, 1, -7};
    int a = 0;
    int b = 0;
    int j = 0;
    int maxSoFar = 0;
    int maxHere = 0;
    for(int i = 0; i < A.length; i++) {
    maxHere += A[i];
    if (maxHere >= maxSoFar) {
    maxSoFar = maxHere;
    a = j;
    b = i;
    }
    if (maxHere <= 0) {
    if (A[i] < 0)
    j = i+1;
    else
    j = i;
    }
    }

    System.out.println("A[" + a + ", " + b + "]");

    ReplyDelete

Subscribe to: Post Comments (Atom)