Maximum Subsequence Score - LeetCode75 Python Solution Explained

The Maximum Subsequence Score problem (LeetCode75) is an advanced array and heap challenge that evaluates your ability to combine sorting, heaps and prefix sums efficiently. It is commonly asked in technical interviews to assess problem-solving skills in subsequence selection and optimization.

In this blog, we will cover the problem statement, provide examples, explain the Python solution step by step with code snippets, analyze time and space complexity, discuss edge cases and explore real-world applications.

Problem Statement

You are given two integer arrays nums1 and nums2 of equal length and an integer k.

The score of a subsequence of length k is calculated as:

sum(nums1[i] for i in subsequence) * min(nums2[i] for i in subsequence)

Return the maximum score you can get among all subsequences of length k.

Example 1

nums1 = [1,3,3,2]
nums2 = [2,1,3,4]
k = 3

Output:

Explanation:

Select subsequence indices [0,2,3] → sum(nums1) = 1+3+2=6, min(nums2) = 2.
Score = 6 * 2 = 12

Example 2

nums1 = [4,2,3,1,1]
nums2 = [7,5,10,9,6]
k = 1

Output:

Explanation:

Select single element at index 2 → nums1=3, nums2=10 → Score = 3 * 10 = 30

Complete Python Solution

from typing import List
from heapq import heappush, heappop
from operator import itemgetter

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        res, prefixSum, minHeap = 0, 0, []

        # Sort pairs by nums2 in descending order
        for a, b in sorted(list(zip(nums1, nums2)), key=itemgetter(1), reverse=True):
            prefixSum += a
            heappush(minHeap, a)

            # Once we have k elements, calculate score
            if len(minHeap) == k:
                res = max(res, prefixSum * b)
                prefixSum -= heappop(minHeap)

        return res

Step-by-Step Explanation

Step 1: Pair Elements and Sort

Combine elements from nums1 and nums2 into tuples and sort by nums2 in descending order. This ensures the current minimum in nums2 is always b during iteration.

for a, b in sorted(list(zip(nums1, nums2)), key=itemgetter(1), reverse=True):

Step 2: Maintain Prefix Sum and Min Heap

Use a min-heap to track the k largest elements from nums1.

Add current a to prefixSum.
Push a into the heap.

prefixSum += a
heappush(minHeap, a)

Step 3: Calculate Score When Heap Size is k

Once we have k elements in the heap:

Calculate current score = prefixSum * b
Update maximum score res if it’s higher
Pop the smallest element from heap to maintain size k

if len(minHeap) == k:
    res = max(res, prefixSum * b)
    prefixSum -= heappop(minHeap)

Step 4: Return Maximum Score

return res

Time and Space Complexity

Time Complexity: O(n log n) → Sorting dominates and heap operations are O(log k) each.
Space Complexity: O(n) → Storing pairs and min-heap of size k.

Edge Cases

k = 1: Only select the element maximizing nums1[i] * nums2[i].
All nums2 are equal: Select the k largest elements from nums1.
Large arrays: Efficient sorting + heap ensures performance.

Real-World Applications

Resource Allocation: Maximizing total output weighted by the minimum efficiency of chosen resources.
Investment Decisions: Choosing top investments considering both profit and risk factors.
Task Scheduling: Selecting tasks that maximize total reward while considering minimum performance constraints.
Portfolio Optimization: Balancing total returns with worst-case component constraints.

Conclusion

The Maximum Subsequence Score problem is a sophisticated example of combining sorting, prefix sums and heaps. By carefully selecting subsequences and maintaining the k largest elements from nums1, we can compute the maximum score efficiently.

This pattern is particularly useful for interview preparation in array optimization, heap management and advanced subsequence selection problems.

Maximum Subsequence Score – LeetCode75 Python Solution Explained