How would I go about finding the maximum sum of an array with the following conditions?

user_5335741 0
Viewed 338

How would I go about finding the maximum sum of an array with the following conditions:

  • The summation must be consecutive.
  • If there exist any 0's, it is consider a "break"
  • The values in the sum of the array cannot be greater than the minimum value

EXAMPLE

 1 0 1 0 0 = 1

 2 0 2 1 1 = 3, why? [2 1 1] -> 1 + 1 + 1

 3 1 3 2 2 = 6, why? [3 2 2] -> 2 + 2 + 2

 4 0 0 3 0 = 4

I tried to think of a bottom up implementation, keeping track of the minimum value thus far while at the same time keeping track of the maximum sum, but I'm getting stuck...

dynamic-programming arrays algorithm
1 Answers

Compute the range in which a given element is the minimum efficiently:

  • Compute the range in which each element is the minimum as (i,j) with i and j excluded. Then with that element as minimum in that range, the sum is (j-i-1)*element.

  • Take maximum of all such values.

  • This should also take care of any zeros present in the array.

If you think about it, it is just another way of asking what is the largest rectangle formed by a histogram.

Lets take an example : [ 3, 1, 3, 2, 2 ]

For the first element 3 : the range in which it is minimum is (-1,1) where -1 is outside of the array and sum is 3*(1-(-1)-1) = 3

For the second element 1 : the range in which it is minimum is (-1,5) and sum is 1*(5-(-1)-1) = 5

....

....

For the fifth element 2 : the range in which it is minimum is (1, 5) and sum is 2*(5-1-1) = 6

For all elements it is : 3 5 3 6 6

The maximum value is 6.

How to compute the range?

  • Left bound:

    For any given element, you look to its left if its greater then take its left bound and go on until you hit an element that is lesser than the current element. Note here that you are not going element by element rather by "bounds". This is important.

  • Right bound:

    You do the same look to the right see if its greater, but keep going to the right until you hit an element that is lesser than the current element.

Code in Java will be :

private static int solve(int[] arr) {
    int n = arr.length;
    int[] leftBound = new int[n];
    int[] rightBound = new int[n];
    leftBound[0] = -1;
    rightBound[n-1] = n;
    for ( int i = 1; i < n; i++ ) {
        int bound = i-1;
        while ( bound >= 0 && arr[bound] >= arr[i] ) {
            bound = leftBound[bound];
        }
        leftBound[i] = bound;
            
    }
    for ( int i = n-2; i >= 0; i-- ) {
        int bound = i+1;
        while ( bound < n && arr[bound] >= arr[i] ) {
            bound = rightBound[bound];
        }
        rightBound[i] = bound;
        
    }
    int res = 0;
    for ( int i = 0; i < n; i++ ) {
        res = Math.max( res, (rightBound[i] - leftBound[i] - 1)*arr[i]);
    }
    return res;
}
user_14103030
Related