How should I practice Maximum Sum from Array Ends?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Maximum Sum from Array Ends associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Maximum Sum from Array Ends

Google● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

Choose exactly k elements from an integer array. Each chosen element must be taken from the current left or right end. Return the largest possible sum.

Equivalently, choose a prefix of length l and a suffix of length k-l, for some 0 <= l <= k. The chosen portions cannot overlap.

For this exercise, assume signed values and permit k=0, which returns 0. Return a 64-bit integer sum.

Function

maxSumFromEnds(nums: int[], k: int) → long

Examples

Example 1

nums = [5,4,3,10,1,1000,2]k = 2return = 1002

The best two picks are 1000 and 2 from the right.

Example 2

nums = [5,4,3,10,1,1000,2]k = 3return = 1007

Choose 5 from the left and 1000,2 from the right.

Example 3

nums = [5,4,3,10,1,1000,2]k = 4return = 1013

Taking 10,1,1000,2 from the right beats the reported 1011 combination. The author acknowledged this correction.

Constraints

For this exercise, assume 0 <= nums.length <= 10^5 and 0 <= k <= nums.length.
-10^6 <= nums[i] <= 10^6.