Maximum Subsequence Score

Updated on 11 June, 2025
Maximum Subsequence Score header image

Problem Statement

In this problem, you are provided with two integer arrays, nums1 and nums2, both having the same length n. Additionally, you are given a positive integer k. Your task is to select a subsequence of indices of length k from nums1. The term "subsequence" here means a subset of the original index set {0, 1, ..., n-1} which can contain zero or more deletions but no reordering.

For any chosen subsequence of indices i0, i1, ..., ik - 1, you need to calculate the score defined as:

  • The sum of the elements in nums1 at these indices multiplied by the minimum of the corresponding elements in nums2 at these indices.
  • Mathematically: (nums1[i0] + nums1[i1] + ... + nums1[ik - 1]) * min(nums2[i0], nums2[i1], ..., nums2[ik - 1]).

The goal is to find and return the maximum possible score by selecting an optimal subsequence of indices.

Examples

Example 1

Input:

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

Output:

12

Explanation:

The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6.
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12.
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.

Example 2

Input:

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

Output:

30

Explanation:

Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

Constraints

  • n == nums1.length == nums2.length
  • 1 <= n <= 105
  • 0 <= nums1[i], nums2[j] <= 105
  • 1 <= k <= n

Approach and Intuition

To understand the optimal approach for solving this problem, consider the fact that maximizing the score depends on two major components:

  1. Maximizing the sum of selected elements from nums1.
  2. Maximizing the minimum value from the corresponding indices in nums2.

Here's a strategy we can consider based on example observations:

  1. Basic Strategy and Insight from Examples:

    • From the examples, it can be observed that to maximize the score, it is often beneficial to select a combination of indices where the minimum value in nums2 (among the selected indices) is relatively high, as well as ensuring the sum of corresponding indices in nums1 is also high.
  2. Sorting for Potential Optimal Solutions:

    • One promising approach could be to sort the indices based on values in nums2 in ascending order and then pick the first k values of indices sorted this way to maximize the minimum in nums2.
    • Similarly, from the selected indices, we sum the k elements in nums1 to maximize the product.
  3. Using a Priority Queue:

    • Maintain a priority queue to help manage the largest sums dynamically as we consider each subset of indices based on their nums2 values.
    • By pushing and popping elements in and out of the queue based on nums1 values, we can manage the largest sum efficiently.
  4. Iterative Combination Generation:

    • Iteratively generate combinations of indices, calculate their scores, and track the maximum.
  5. Optimization Thoughts:

    • Since directly generating all combinations for large n can be computationally intensive (since it involves combinations of n select k), focus on heuristic or greedy approaches that make logical sense based on the constraints of maximizing the core components in the score formula.

By considering these approaches, especially focusing on the interplay between maximizing the sum from nums1 and maximizing the corresponding minimum from nums2 based on sorting or the use of a priority queue, you can develop a strategy that efficiently finds an optimal or near-optimal solution.

Solutions

  • Java
  • Python
java
class Solution {
    public long maximumScore(int[] array1, int[] array2, int limit) {
        int length = array1.length;
        int[][] sortedPairs = new int[length][2];
        for (int i = 0; i < length; ++i) {
            sortedPairs[i] = new int[]{array1[i], array2[i]};
        }
        Arrays.sort(sortedPairs, (x, y) -> y[1] - x[1]);
            
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(limit, (a, b) -> a - b);
        long maxSum = 0;
        for (int i = 0; i < limit; ++i) {
            maxSum += sortedPairs[i][0];
            minHeap.add(sortedPairs[i][0]);
        }
            
        long result = maxSum * sortedPairs[limit - 1][1];
            
        for (int i = limit; i < length; ++i) {
            maxSum += sortedPairs[i][0] - minHeap.poll();
            minHeap.add(sortedPairs[i][0]);
            result = Math.max(result, maxSum * sortedPairs[i][1]);
        }
            
        return result;
    }
}

The provided Java solution aims to identify the maximum score of a subsequence within two integer arrays, constrained by a specified limit. The problem involves pairing the elements from the two arrays, sorting the pairs based on the second array's values in descending order, and then calculating scores to identify the maximal result under given constraints using efficient data structures and algorithms.

Here’s an explanation of how the solution works:

  1. Initialize a 2D array sortedPairs to store elements from array1 and array2 as pairs.
  2. Sort sortedPairs by the second element of each pair in descending order. This prioritization ensures that the most significant multipliers from array2 are considered first for higher score potential.
  3. Utilize a PriorityQueue (minHeap) to maintain the smallest elements from array1 that form part of the maximum score calculation. This heap helps efficiently find and remove the smallest element when adding a new one from sortedPairs.
  4. Calculate the initial potential max score using the top elements up to the specified limit from the sorted pairs.
  5. Iterate through the rest of the pairs in sortedPairs. For each element:
    • Update the score by removing the smallest element in the heap and adding the current element.
    • Calculate the potential result with the updated score and the current multiplier from array2.
    • Update the result to store the maximum score found so far.
  6. Finally, the maximum score found, as per given constraints, is returned.

This method leverages sorting and a min-heap to efficiently manage and update the elements contributing to the score, ensuring optimal time complexity and performance for large inputs.

python
class Solution:
    def maxScoreCalculation(self, list1: List[int], list2: List[int], count: int) -> int:
        # Organize pairs by second element of each pair in descending order.
        combined = [(elem1, elem2) for elem1, elem2 in zip(list1, list2)]
        combined.sort(key=lambda element: -element[1])
            
        # Utilize a min heap for the largest 'count' elements based on list1's values.
        heap = [v[0] for v in combined[:count]]
        heap_sum = sum(heap)
        heapq.heapify(heap)
            
        # Initial calculation for maximum score using the smallest of kth elements from list2.
        max_result = heap_sum * combined[count - 1][1]
            
        # Review each value from list2 considering it as the minimum in the product score.
        for index in range(count, len(list1)):
            # Update the heap by replacing the smallest element and adding the current element from list1.
            heap_sum -= heapq.heappop(heap)
            heap_sum += combined[index][0]
            heapq.heappush(heap, combined[index][0])
                
            # Recalculate the potential max result.
            max_result = max(max_result, heap_sum * combined[index][1])
            
        return max_result

The solution provided aims to calculate the maximum subsequence score by considering two integer lists, list1 and list2, along with a given integer count. The method maxScoreCalculation achieves this through a series of strategic operations:

  • Pairs elements from list1 and list2 into tuples, sorts these tuples based on the elements from list2 in descending order.
  • Utilizes a min-heap data structure to maintain the count largest elements derived from list1 values, creating a sum of these maximal elements termed heap_sum.
  • Computes an initial potential maximum score using the smallest value among the top count elements of list2.
  • Iterates through elements of list2, starting from the count index to the end. In each iteration:
    • Adjusts the heap by replacing the smallest element with the current element from list1, ensuring it continuously reflects the count largest values.
    • Recalculates the maximum score using the updated heap_sum and the current element from list2.

The process concludes by returning the max_result, which holds the highest score computed across all iterations. This approach efficiently harnesses sorting and heap operations to ascertain the optimal scoring sequence based on the criteria set by list1, list2, and count.

Comments

No comments yet.