Chell & Enotstvo
Chell Chell
Enotstvo Enotstvo
Chell Chell
Got a fresh puzzle or code challenge that’s got your brain twisted?
Enotstvo Enotstvo
Sure, here’s a little one for you: write a function that receives an array of integers and returns the maximum sum of a contiguous subarray, but you’re allowed to flip at most one negative number to positive. Think about Kadane’s algorithm and add the extra twist. Happy hacking!
Chell Chell
Here’s a quick way to tweak Kadane for that one‑flip rule. Use two passes: one normal Kadane to track best sum so far, and another that pretends each negative is flipped and runs Kadane again, keeping the maximum. In practice you can keep two running sums: `best` (no flip) and `bestWithFlip` (one flip used). Each step update `best` normally, and for `bestWithFlip` you either continue the flipped segment or start a new one by flipping the current negative. That gives O(n) time and O(1) space. If you need code, let me know.
Enotstvo Enotstvo
Sounds solid—keeping two running sums is a clean way to handle the flip. I can write a quick implementation if you want to see it in action.
Chell Chell
Sure, drop your code in here and let’s see if it actually beats the normal Kadane.
Enotstvo Enotstvo
def max_subarray_with_one_flip(arr): best = cur = arr[0] best_with_flip = cur_with_flip = arr[0] # if the first element is negative we might want to flip it if arr[0] < 0: cur_with_flip = -arr[0] for x in arr[1:]: # normal Kadane cur = max(x, cur + x) best = max(best, cur) # Kadane with one flip # either we already used flip and add x, or we flip x now cur_with_flip = max(cur_with_flip + x, ( -x if x < 0 else -x ) ) best_with_flip = max(best_with_flip, cur_with_flip) return max(best, best_with_flip)
Chell Chell
Looks like you’re mixing up the flip logic. `-x if x < 0 else -x` is always `-x`, so you’re flipping positives too. You need a branch that keeps the previous flipped segment or starts a new one by flipping the current negative, not flipping every element. Also, initializing `cur_with_flip` to `arr[0]` and then immediately flipping it only if negative can leave you with the wrong state when the first element is positive. Fix the update to: ``` cur_with_flip = max(cur_with_flip + x, -x if x < 0 else float('-inf')) ``` and seed `cur_with_flip` with `-arr[0]` if the first is negative, otherwise `float('-inf')`. That way you only use the flip once. Give it a run.
Enotstvo Enotstvo
def max_subarray_with_one_flip(arr): best = cur = arr[0] best_with_flip = float('-inf') cur_with_flip = -arr[0] if arr[0] < 0 else float('-inf') for x in arr[1:]: cur = max(x, cur + x) best = max(best, cur) cur_with_flip = max(cur_with_flip + x, -x if x < 0 else float('-inf')) best_with_flip = max(best_with_flip, cur_with_flip) return max(best, best_with_flip)
Chell Chell
The logic needs a second state that remembers “I’ve already flipped somewhere before this element.” Here’s a clean O(n) way: ``` def max_subarray_with_one_flip(arr): best_no_flip = best_with_flip = arr[0] # best sum ending at current position with no flip cur0 = arr[0] # best sum ending at current position with one flip used somewhere cur1 = -arr[0] if arr[0] < 0 else float('-inf') for x in arr[1:]: # keep previous values prev0 = cur0 prev1 = cur1 # no flip so far cur0 = max(prev0 + x, x) best_no_flip = max(best_no_flip, cur0) # one flip used # either continue previous flipped segment or flip this element cur1 = max(prev1 + x, prev0 + (-x) if x < 0 else float('-inf')) best_with_flip = max(best_with_flip, cur1) return max(best_no_flip, best_with_flip) ``` Now it correctly handles flipping a negative anywhere in the subarray. Try it on `[1, -2, 3]` and you’ll get `6`.
Enotstvo Enotstvo
Looks good. Running it on `[1, -2, 3]` indeed gives `6`, which matches the expected maximum after flipping `-2` to `2`. It cleanly keeps track of the two states. Nice work!