| # | Title | Difficulty | Tag | Time, ms | Time, %

|------|----------------|-------------|-------------|----------|---------

| 2542 |[Maximum Subsequence Score](src/main/java/g2501_2600/s2542_maximum_subsequence_score/Solution.java)| Medium | Array, Sorting, Greedy, Heap_(Priority_Queue) | 94 | 84.75

| 2541 |[Minimum Operations to Make Array Equal II](src/main/java/g2501_2600/s2541_minimum_operations_to_make_array_equal_ii/Solution.java)| Medium | Array, Math, Greedy | 3 | 100.00

| 2540 |[Minimum Common Value](src/main/java/g2501_2600/s2540_minimum_common_value/Solution.java)| Easy | Array, Hash_Table, Binary_Search, Two_Pointers | 0 | 100.00

| 2538 |[Difference Between Maximum and Minimum Price Sum](src/main/java/g2501_2600/s2538_difference_between_maximum_and_minimum_price_sum/Solution.java)| Hard | Array, Dynamic_Programming,Tree, Depth_First_Search | 43 | 95.19

| 2538 |[Difference Between Maximum and Minimum Price Sum](src/main/java/g2501_2600/s2538_difference_between_maximum_and_minimum_price_sum/Solution.java)| Hard | Array, Dynamic_Programming,Depth_First_Search, Tree | 43 | 95.19

| 2537 |[Count the Number of Good Subarrays](src/main/java/g2501_2600/s2537_count_the_number_of_good_subarrays/Solution.java)| Medium | Array, Hash_Table, Sliding_Window | 38 | 99.07

| 2536 |[Increment Submatrices by One](src/main/java/g2501_2600/s2536_increment_submatrices_by_one/Solution.java)| Medium | Array, Matrix, Prefix_Sum | 12 | 88.15

| 2535 |[Difference Between Element Sum and Digit Sum of an Array](src/main/java/g2501_2600/s2535_difference_between_element_sum_and_digit_sum_of_an_array/Solution.java)| Easy | Array, Math | 3 | 77.42

packageg2501_2600.s2542_maximum_subsequence_score;

importjava.util.Arrays;

importjava.util.PriorityQueue;

publicclassSolution {

privatestaticclassPairInfo {

intval1;

intval2;

publicPairInfo(intval1,intval2) {

this.val1 =val1;

this.val2 =val2;

}

}

publiclongmaxScore(int[]nums1,int[]nums2,intk) {

intn =nums1.length;

PairInfo[]nums =newPairInfo[n];

for (inti =0;i <n; ++i) {

nums[i] =newPairInfo(nums1[i],nums2[i]);

}

Arrays.sort(

nums,

(a,b) -> {

if (a.val2 ==b.val2) {

returna.val1 -b.val1;

}

returna.val2 -b.val2;

});

longsum =0;

longans =0;

PriorityQueue<Integer>pq =newPriorityQueue<>();

for (inti =n -1;i >=0; --i) {

intminVal =nums[i].val2;

while (pq.size() >k -1) {

sum -=pq.poll();

}

sum +=nums[i].val1;

pq.add(nums[i].val1);

if (pq.size() ==k) {

ans =Math.max(ans,sum *minVal);

}

}

returnans;

}

}

2542\. Maximum Subsequence Score

Medium

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 <code>i₀</code>, <code>i₁</code>, ..., <code>i_{k - 1}</code>, 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: <code>(nums1[i₀] + nums1[i₁] +...+ nums1[i_{k - 1}]) * min(nums2[i₀] , nums2[i₁], ... ,nums2[i_{k - 1}])</code>.

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:**

**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:**

* <code>1 <= n <= 10⁵</code>

* <code>0 <= nums1[i], nums2[j] <= 10⁵</code>

packageg2501_2600.s2542_maximum_subsequence_score;

importstaticorg.hamcrest.CoreMatchers.equalTo;

importstaticorg.hamcrest.MatcherAssert.assertThat;

importorg.junit.jupiter.api.Test;

classSolutionTest {

voidmaxScore() {

assertThat(

newSolution().maxScore(newint[] {1,3,3,2},newint[] {2,1,3,4},3),

equalTo(12L));

}

voidmaxScore2() {

assertThat(

newSolution().maxScore(newint[] {4,2,3,1,1},newint[] {7,5,10,9,6},1),

equalTo(30L));

}

}