CODEWITHSUNDEEP
arraysalgorithmdynamic-programming
user
user

Reputation: 914

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

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

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...

Upvotes: 2

Views: 446

Answers (1)

SomeDude
SomeDude

Reputation: 14238

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

Upvotes: 2

Related Questions