3428. Maximum and Minimum Sums of at Most Size K Subsequences - Detailed Explanation

Problem Statement

You’re given an integer array nums and an integer k. A subsequence of nums is any sequence you can form by deleting zero or more elements without changing the relative order of the remaining elements. You want two values:

• The maximum sum obtainable by any subsequence of size at most k.
• The minimum sum obtainable by any subsequence of size at most k.

Return an array [maxSum, minSum] containing these two values.

Examples

Example 1

Input:  nums = [3, -1, 4, -2, 5], k = 3
Output: [12, -3]
Explanation:
  For maxSum, pick the three largest positives [5,4,3] → sum = 12
  For minSum, pick the two most negative [-2,-1] (you could pick up to 3 but adding 3rd positive would increase sum) → sum = -3

Example 2

Input:  nums = [-5, -2, -3, -4], k = 2
Output: [-7, -9]
Explanation:
  For maxSum, pick at most 2 elements: two “largest” negatives are [-2,-3] → sum = -5? Actually we can pick zero to get 0 which is larger than any negative, so maxSum = 0.
  For minSum, pick the two smallest [-5,-4] → sum = -9

Example 3

Input:  nums = [1,2,3], k = 5
Output: [6, 0]
Explanation:
  You can pick all three positives for maxSum → 6
  For minSum, best is to pick no elements (sum = 0) rather than any positive

Constraints

• 1 ≤ nums.length ≤ 10⁵
• -10⁹ ≤ nums[i] ≤ 10⁹
• 1 ≤ k ≤ nums.length

Hints

1. Since a subsequence may skip elements arbitrarily, ordering doesn’t matter—only the values.
2. To maximize a sum with up to k elements, you only ever want to pick the largest positive values (or pick none if all are non‑positive).
3. To minimize a sum with up to k elements, you only ever want to pick the smallest negative values (or pick none if all are non‑negative).
4. Sorting the array (or using selection algorithms/heaps to find the top‑k) lets you compute both answers in O(n log n) or O(n + k log n).

Approach

1. Sort and Greedy Pick

1. Sort nums in descending order.
2. MaxSum:
   • Initialize maxSum = 0, count = 0.
   • Iterate from the largest down, adding nums[i] to maxSum if it’s positive and count < k.
   • Stop early if you hit zero or negative or have picked k elements.
3. MinSum:
   • Initialize minSum = 0, count = 0.
   • Iterate from the smallest up (i.e. sort in ascending or traverse the end of descending), adding nums[i] to minSum if it’s negative and count < k.
   • Stop when you hit zero or positive or have picked k elements.
4. Return [maxSum, minSum].

2. Selection via Heaps (O(n + k log n))

• Maintain a max‑heap of all negative numbers (to pick the k smallest).
• Maintain a min‑heap of all positive numbers (to pick the k largest).
• Pop up to k times from each heap, summing as appropriate; skip popping if the top worsens the objective (e.g. don’t pop a positive when minimizing).

Step‑by‑Step Walkthrough (Example 1)

nums = [3, -1, 4, -2, 5], k = 3
Sorted descending → [5,4,3,-1,-2]

Compute maxSum:
  pick 5 → maxSum=5, cnt=1
  pick 4 → maxSum=9, cnt=2
  pick 3 → maxSum=12, cnt=3 → reached k, stop

Compute minSum:
  traverse from the back of sorted descending (i.e. ascending): [-2,-1,3,4,5]
  pick -2 → minSum=-2, cnt=1
  pick -1 → minSum=-3, cnt=2
  cnt=2<k=3 but next is +3, stop (adding makes sum larger)

Result → [12, -3]

Complexity Analysis

• Time:
  • Sorting takes O(n log n).
  • One linear pass to accumulate picks.
  • Overall: O(n log n).
• Space: O(1) extra beyond the input (or O(n) if your sort isn’t in‑place).

Python Code

Java Code