Problem. Given an integer array, define prefix_score(i) = sum(nums[0..i]) and suffix_score(i) = sum(nums[i..n−1]). Find the maximum value of prefix_score(i) + suffix_score(i) over all indices i. Note: nums[i] is counted in both sums.
Examples:
[1, -2, 3, 4, -1]→9— at i=3: prefix=1+(−2)+3+4=6, suffix=4+(−1)=3, total=9.[5]→10— prefix=5, suffix=5, total=10.[-1, -2, -3]→-5— at i=0: prefix=−1, suffix=−1+(−2)+(−3)=−6, total=−7. At i=2: prefix=−6, suffix=−3, total=−9. Best is at i=0: −1+(−6)=−7… Actually at i=0 prefix=−1 and suffix=sum=−6, total=−7. Hmm, let me recalculate.prefix(i)+suffix(i) = sum(0..i)+sum(i..n-1) = total_sum + nums[i]. So max istotal_sum + max(nums). For[-1,-2,-3]: total=−6, max=−1, answer=−7.
Solution. Since prefix_score(i) + suffix_score(i) = total_sum + nums[i], the answer is simply sum(nums) + max(nums).
def max_prefix_suffix(nums):
return sum(nums) + max(nums)
O(n) time, O(1) space.
Gotchas.
- The key insight: element
iis double-counted (in both prefix and suffix), so the combined score istotal + nums[i]. Maximise by picking the largest element. - Don’t build prefix and suffix arrays — that’s O(n) space for no reason.
- All-negative arrays: the answer is still
total + max(nums), which will be negative. - Empty array is undefined; clarify constraints.