Sponsored
Sponsored
Solve with full IDE support and test cases
Use these hints if you're stuck. Try solving on your own first.
The problem can be solved using dynamic programming.
Since we can always start a new subarray, the problem is the same as selecting some elements in the array and flipping their signs to negative to maximize the sum. However, we cannot flip the signs of 2 consecutive elements, and the first element in the array cannot be negative.
Let <code>dp[i][0/1]</code> be the largest sum we can get for prefix <code>nums[0..i]</code>, where <code>dp[i][0]</code> is the maximum if the <code>i<sup>th</sup></code> element wasn't flipped, and <code>dp[i][1]</code> is the maximum if the <code>i<sup>th</sup></code> element was flipped.
Based on the restriction:<br /> <code>dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + nums[i]</code><br /> <code>dp[i][1] = dp[i - 1][0] - nums[i]</code>
The initial state is:<br /> <code>dp[1][0] = nums[0] + nums[1]</code><br /> <code>dp[1][1] = nums[0] - nums[1]</code><br /> and the answer is <code>max(dp[n - 1][0], dp[n - 1][1])</code>.
Can you optimize the space complexity?