Problem link : Question Paper (PDF), Problem 2 is the problem I need help with

Hey, can anybody help me with solving this problem?

I have thought of an algorithm to solve this problem. Refer below.

- First, find the max subarray with Kadane’s. If that’s the full array, we are done.
- Otherwise, we, now expand our reach of the max sum by moving left and right, one by one, excluding negative values.

But now I am having some problems.

- How do we move ahead, that is, what is the next step in the above algorithm. There are some cases where few negative numbers are still left and it is wise to exclude them or that the sum of the rest positive elements suffices to “deal with” the remaining negative values, so we should include all of the array or some more portion of the array.
- What if there are more than one segments with sum equalling max sum?

Can anybody please provide me with the correct algorithm to solve this problem and a possibly, pseudocode on how to code this problem (assume c++ stl).

Thanks