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