Shortest subsequence with maximum sum
Filed under Amazon
Free read 2 of 3To maximize sum, include all positive numbers. If all numbers are negative, the max sum is the single largest (least negative) element.
The question
Find the shortest subsequence of an array that results in the maximum possible sum.
Constraints
- Array can contain negative numbers
- Subsequence must be non-empty
- Maximize sum first, minimize length second
Examples
- Input
- [1, -2, 3, 3]
- Output
- [3, 3]
- Why
- Max sum is 6, shortest subsequence is [3, 3].
Approach
To maximize sum, include all positive numbers. If all numbers are negative, the max sum is the single largest (least negative) element.
Zeros do not change the sum but increase length, so exclude them unless the array contains only zeros.
Collect all positive numbers. If empty, pick the max element.
Tips
- What they are testing: Tests greedy logic and array manipulation.
- Common mistake: Including negative numbers that decrease the sum.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.