Solve programming task with follow-ups

Question

Pure programming problem solving: implement the core algorithmic solution, then extend it to (1) support a constraint of consecutive N elements and (2) an optimization that uses only suffix-related information.

Part 1: Maximum Contiguous Subarray Sum

Given an integer array nums, return the maximum possible sum of any non-empty contiguous subarray. If nums is empty, return 0.

Constraints

• 0 <= len(nums) <= 200000
• -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input: ([-2, 1, -3, 4, -1, 2, 1, -5, 4],)
Output: 6

Explanation: The best contiguous subarray is [4, -1, 2, 1], which sums to 6.

Example 2

Input: ([1],)
Output: 1

Explanation: A single element array has only one non-empty contiguous subarray.

Hints

1. Track the best sum of a subarray that must end at the current index.
2. If extending the current subarray is worse than starting fresh at nums[i], start a new subarray there.

Part 2: Maximum Sum of Exactly N Consecutive Elements

Given an integer array nums and an integer k, return the maximum sum of any contiguous subarray of length exactly k. If k is invalid (k < 1 or k > len(nums)), return None.

Constraints

• 0 <= len(nums) <= 200000
• 0 <= k <= 200000
• -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input: ([1, 2, 3, 4, 5], 2)
Output: 9

Explanation: The best window of length 2 is [4, 5].

Example 2

Input: ([4, -1, 2, 1], 4)
Output: 6

Explanation: The only valid window is the entire array.

Hints

1. First compute the sum of the first window of size k.
2. When moving the window by one step, subtract the outgoing element and add the incoming element.

Part 3: Maximum Total of Two Non-Overlapping Subarrays Using Suffix Bests

Given an integer array nums, choose two non-overlapping, non-empty contiguous subarrays so that their total sum is as large as possible. Return that maximum total. If fewer than 2 elements are provided, return None. A brute-force approach is too slow; solve it in O(n) by precomputing the best subarray sum available in each suffix.

Constraints

• 0 <= len(nums) <= 200000
• -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input: ([1, 3, -1, 2, -1, 2],)
Output: 7

Explanation: One optimal choice is [1, 3] and [2, -1, 2], for a total of 4 + 3 = 7.

Example 2

Input: ([-1, -2, -3, -4],)
Output: -3

Explanation: The best choice is two single-element subarrays: [-1] and [-2].

Hints

1. Imagine splitting the array between i and i + 1. You need the best subarray on the left side and the best subarray on the right side.
2. Precompute, for every index, the best subarray sum contained entirely in the suffix starting there.