Maximum Subsequence Score

Problem

You are given two integer arrays nums1 and nums2, both of length n, and a positive integer k.

You must choose a subsequence of exactly k indices i_1, i_2, ..., i_k (the indices, not the values, must be distinct). For a chosen set of indices, the score is defined as:

(sum of the selected nums1 values) × (minimum of the selected nums2 values)

That is, add up the nums1 entries at your chosen indices, then multiply that sum by the smallest nums2 entry among those same indices.

Return the maximum possible score over all valid choices of k indices.

Examples

• Input: nums1 = [1, 3, 3, 2], nums2 = [2, 1, 3, 4], k = 3 → Output: 12 Pick indices {0, 2, 3}. nums1 sum = 1 + 3 + 2 = 6; nums2 min = min(2, 3, 4) = 2; score = 6 × 2 = 12. No other triple beats it.
• Input: nums1 = [4, 2, 3, 1, 1], nums2 = [7, 5, 10, 9, 6], k = 1 → Output: 30 With k = 1, score is just nums1[i] × nums2[i]. Index 2 gives 3 × 10 = 30, the best single pick.
• Input: nums1 = [2, 1, 14, 12], nums2 = [11, 7, 5, 5], k = 2 → Output: 130 Indices {2, 3} give sum 14 + 12 = 26, min min(5, 5) = 5, score 130. Other pairs score lower: {0, 3} gives sum 14, min 5, score 70; {0, 1} gives sum 3, min 7, score 21.

Constraints

• n == nums1.length == nums2.length, with 1 <= n <= 10^5.
• 0 <= nums1[i], nums2[j] <= 10^5.
• 1 <= k <= n.

The 10^5 size rules out anything close to trying all C(n, k) subsets — you need roughly O(n log n).

Think about it first

TL;DR

Sort pairs by nums2 descending, sweep while keeping the k largest nums1 values in a min-heap with a running sum — O(n log n) time, O(n) space.

Approach 1 — Brute force: try every k-subset

Enumerate every combination of k indices, compute each score, and keep the maximum.

from itertools import combinations
from typing import List

def maxScore(nums1: List[int], nums2: List[int], k: int) -> int:
    n = len(nums1)
    best = 0
    for combo in combinations(range(n), k):
        total = sum(nums1[i] for i in combo)
        minimum = min(nums2[i] for i in combo)
        best = max(best, total * minimum)
    return best

Complexity: O(C(n, k) · k) time. With up to C(10^5, k) subsets, this is far too slow for the constraints. It is included only to state the definition precisely.

Approach 2 — Sort by nums2 desc + min-heap of the top-k nums1

The multiplier is the minimum nums2 in the chosen set, so fix it by sorting. Sort all (nums2[i], nums1[i]) pairs by nums2 descending and sweep left to right. When you reach a pair, its nums2 is the smallest among everything seen so far, so treat it as the minimum multiplier. Every element seen so far has a nums2 at least this large, so any k of them form a valid set; to maximize the score, pick the k largest nums1 values. A min-heap of size k plus a running sum does this: push each nums1, and when the heap grows past k, pop the smallest and subtract it from the sum. Whenever the heap holds exactly k items, running_sum × current_nums2 is a candidate answer.

flowchart TD
    A[Next pair, by nums2 descending] --> B[Push nums1 to min-heap, add to running sum]
    B --> C{Heap size greater than k?}
    C -->|Yes| D[Pop smallest nums1, subtract from sum]
    C -->|No| E{Heap size equals k?}
    D --> E
    E -->|Yes| F[Candidate = running sum times current nums2, update best]
    E -->|No| G[Skip: subsequence not yet complete]

import heapq
from typing import List

def maxScore(nums1: List[int], nums2: List[int], k: int) -> int:
    pairs = sorted(zip(nums2, nums1), reverse=True)  # by nums2 desc

    min_heap: List[int] = []
    running_sum = 0
    best = 0

    for n2, n1 in pairs:
        heapq.heappush(min_heap, n1)
        running_sum += n1
        if len(min_heap) > k:
            running_sum -= heapq.heappop(min_heap)
        if len(min_heap) == k:
            best = max(best, running_sum * n2)

    return best

Walkthrough on nums1 = [1, 3, 3, 2], nums2 = [2, 1, 3, 4], k = 3:

• Pairs sorted by nums2 desc: (4, 2), (3, 3), (2, 1), (1, 3).
• (4, 2): heap [2], sum 2, size 1 < 3.
• (3, 3): heap [2, 3], sum 5, size 2 < 3.
• (2, 1): heap [1, 3, 2], sum 6, size 3 → candidate 6 × 2 = 12. best = 12.
• (1, 3): push 3 → sum 9, size 4 > 3, pop smallest 1 → sum 8, heap [2, 3, 3], size 3 → candidate 8 × 1 = 8. best stays 12.

Answer: 12, matching the example (indices {0, 2, 3}).

Complexity: O(n log n) time (the sort dominates; each of the n heap operations is O(log k)), O(n) space for the sorted pairs and the heap.

Common pitfalls

• Sorting by nums1 instead of nums2. The multiplier is the min of nums2; that is what must be pinned by the sort order.
• Only evaluating when the heap is exactly size k. Before you have k elements the subsequence is incomplete; computing a score early gives wrong answers.
• Forgetting to subtract the popped value from the running sum. The sum must always equal the total of the values currently in the heap.
• Initializing best too high. Values can be 0 (e.g. a nums1 entry of 0), so best = 0 is a safe floor; never seed it with a made-up large negative that could survive if all scores are 0.

Pattern takeaway

When a score mixes an additive term with a bottleneck (min/max) term, fix the bottleneck by sorting on it, then let a size-k heap greedily maintain the best additive part among everything still eligible. “Sort to fix the minimum, heap to keep the top-k” recurs across many two-array optimization problems.