2542. Maximum Subsequence Score
You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.
For chosen indices i0, i1, …, ik - 1, your score is defined as:
- The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
- It can defined simply as: (nums1[i0] + nums1[i1] +…+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], … ,nums2[ik - 1]).
Return the maximum possible score.
A subsequence of indices of an array is a set that can be derived from the set {0, 1, …, n-1} by deleting some or no elements.
Example 1:
Example 2:
Constraints:
- n == nums1.length == nums2.length
- 1 < = n < = 1 0 5 1 <= n <= 10^5 1<=n<=105
- 0 < = n u m s 1 [ i ] , n u m s 2 [ j ] < = 1 0 5 0 <= nums1[i], nums2[j] <= 10^5 0<=nums1[i],nums2[j]<=105
- 1 <= k <= n
From: LeetCode
Link: 2542. Maximum Subsequence Score
Solution:
Ideas:
-
Data Structure (Data): A struct that pairs elements from nums1 and nums2 together. This allows sorting and processing based on the elements of nums2 while keeping the corresponding nums1 values paired.
-
Sorting (qsort with cmpfunc): The array of Data structs is sorted in descending order based on nums2 values. This sorting helps in selecting the k elements with the highest nums2 values first, which is critical in finding the minimum nums2 value in each iteration.
-
Min Heap Operations:
- Heapify (heapifyMinHeap): Maintains the min heap property in the heap. This is used when the root is deleted or when a new element is inserted.
- Insertion (insertToHeap): Inserts a new element into the min heap. This operation is used to keep track of k elements from nums1.
- Deletion (deleteRootFromHeap): Removes the root (minimum element) from the min heap. This is necessary when moving the window of size k forward.
- Main Logic (maxScore function):
- An array of Data structs is created and sorted.
- A min heap is used to keep track of the k elements from nums1.
- In each iteration, a new element from the sorted Data array is added to the heap, and the minimum element is removed if the heap size exceeds k.
- The sum of the k elements in the heap and the minimum nums2 value from the k elements chosen so far are used to calculate the score.
- The algorithm looks for the maximum score as it iterates through the sorted Data array.
Code:
typedef long long LL;
typedef struct{
int nums1;
int nums2;
}Data;
int cmpfunc (const void * a, const void * b){
int anums2 = ((Data*)a)->nums2;
int bnums2 = ((Data*)b)->nums2;
return (bnums2 - anums2);
}
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void heapifyMinHeap(int* nums, int numsSize, int parentIndex){
int smallest = parentIndex;
int leftChild = (smallest << 1) + 1;
int rightChild = (smallest << 1) + 2;
if((leftChild < numsSize) && (nums[leftChild] < nums[smallest])){
smallest = leftChild;
}
if((rightChild < numsSize) && (nums[rightChild] < nums[smallest])){
smallest = rightChild;
}
if(smallest != parentIndex){
swap(&nums[smallest], &nums[parentIndex]);
heapifyMinHeap(nums, numsSize, smallest);
}
}
void deleteRootFromHeap(int* nums, int numsSize){
swap(&nums[0], &nums[--numsSize]);
heapifyMinHeap(nums, numsSize, 0);
}
void insertToHeap(int* nums, int numsSize, int new){
nums[numsSize++] = new;
int childIndex = numsSize - 1;
int parentIndex = (childIndex - 1) >> 1;
while((childIndex > 0) && (nums[childIndex] < nums[parentIndex])){
swap(&nums[childIndex], &nums[parentIndex]);
childIndex = parentIndex;
parentIndex = (childIndex - 1) >> 1;
}
}
long long maxScore(int* nums1, int nums1Size, int* nums2, int nums2Size, int k){
Data* data = (Data*)malloc(nums2Size * sizeof(Data));
for(int i = 0; i < nums2Size; i++){
data[i].nums1 = nums1[i];
data[i].nums2 = nums2[i];
}
qsort(data, nums2Size, sizeof(Data), cmpfunc);
int* minHeap = (int*)calloc(k + 1, sizeof(int));
int heapSize = 0;
LL sumNum1 = 0;
LL minNums2 = 0;
LL maxScore = 0;
LL score = 0;
for(int i = 0; i < k; i++){
sumNum1 += data[i].nums1;
minNums2 = data[i].nums2;
insertToHeap(minHeap, heapSize++, data[i].nums1);
}
maxScore = sumNum1 * minNums2;
for(int i = k; i < nums2Size; i++){
sumNum1 += data[i].nums1;
minNums2 = data[i].nums2;
insertToHeap(minHeap, heapSize++, data[i].nums1);
sumNum1 -= minHeap[0];
deleteRootFromHeap(minHeap, heapSize--);
score = sumNum1 * minNums2;
if(score > maxScore){
maxScore = score;
}
}
free(data);
free(minHeap);
return maxScore;
}