Find max sum of elements in an array ( with twist)

Question

Given a array with +ve and -ve integer , find the maximum sum such that you are not allowed to skip 2 contiguous elements ( i.e you have to select at least one of them to move forward).

eg :-

10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3

Output : 10+20+30-10+40-1 = 89

Solution 1

Use a recurrence that accounts for that:

dp[i] = max(dp[i - 1] + a[i], <- take two consecutives
            dp[i - 2] + a[i], <- skip a[i - 1])

Base cases left as an exercise.

Solution 2

This problem can be solved using Dynamic Programming approach.

Let arr be the given array and opt be the array to store the optimal solutions. opt[i] is the maximum sum that can be obtained starting from element i, inclusive.

opt[i] = arr[i] + (some other elements after i)

Now to solve the problem we iterate the array arr backwards, each time storing the answer opt[i]. Since we cannot skip 2 contiguous elements, either element i+1 or element i+2 has to be included in opt[i].

So for each i, opt[i] = arr[i] + max(opt[i+1], opt[i+2])

See this code to understand:

int arr[n];  // array of given numbers. array size = n.
nput(arr, n);   // input the array elements (given numbers)

int opt[n+2];   // optimal solutions. 
memset(opt, 0, sizeof(opt));    // Initially set all optimal solutions to 0.

for(int i = n-1; i >= 0; i--) {
    opt[i] = arr[i] + max(opt[i+1], opt[i+2]);
}

ans = max(opt[0], opt[1])   // final answer.

Observe that opt array has n+2 elements. This is to avoid getting illegal memory access exception (memory out of bounds) when we try to access opt[i+1] and opt[i+2] for the last element (n-1).

See the working implementation of the algorithm given above

Solution 3

If you see a +ve integer add it to the sum. If you see a negative integer, then inspect the next integer pick which ever is maximum and add it to the sum.

10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3

For this add 10, 20, 30, max(-10, -50), 40 max(-50, -1) and since there is no element next to -3 discard it.

The last element will go to sum if it was +ve.

Comments

[user1057741]

base case : if( input[0] > 0 && input[1] >0 ) then dp[0] = input[0] && dp[1] = input[0] + input[1]; else dp[0] = input[0]; dp[1] = max(dp[i-1] + arr[1] , dp[i-1] ); is this fine ?

[IVlad]

@user1057741 - I wouldn't complicate things so much. dp[-1] = 0, dp[0] = a[0]. Now just run the dp. I don't know why you compare with 0...

[M. Adeel Khalid]

Explain how you solved the problem asked by the user.

[Plutian]

Hi and welcome to stackoverflow, and thank you for your answer. Rather than just posting a block of code, can you give a short explanation to what the issue is you solved and how you solved it? This will help people who find this question in the future to better understand the issue and how to deal with it.