Maximum Score

This problem is from a hiring challenge so please don’t ask for link.

We have N numbers, we have to find the maximum sum of these number by flipping at least one or more numbers consecutively. We can apply flipping only once.
Flipping change the sign of the number (means if a number in less than zero it become greater than zero with same value and vice versa)

-2 after flipping become 2
5 after flipping becomes -5

My approach : Find the subarray with minimum sum(msum). Take sum all elements then
ans = sum - 2 * msum

What’s wrong with this approach as I got only partial marks ?

Constraints :
1 <= N <= 500
-1000 <= A[i] <= 1000

Excluding empty subarrays, presumably? (i.e. the min subarray would be negative (not zero) in the case where all numbers are negative).

I can’t think of a situation where this would fail, offhand - do you have your actual code?


You don’t give the ranges of the numbers - is there the possibility of overflow?

Constraints were too low, Yes subarray can be empty for that case msum is minimum element of the array.

No, I don’t have code because Copy pasting was not allowed.