3430. Maximum and Minimum Sums of at Most Size K Subarrays

Posted on Edited on In

3430. Maximum and Minimum Sums of at Most Size K Subarrays

Description

You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all subarrays with at most k elements.

Example 1:

1
2
3
Input: nums = [1,2,3], k = 2

Output: 20

Explanation:

The subarrays of nums with at most 2 elements are:

SubarrayMinimumMaximumSum
[1]112
[2]224
[3]336
[1, 2]123
[2, 3]235
Final Total20

The output would be 20.

Example 2:

Input: nums = [1,-3,1], k = 2

Output: -6

Explanation:

The subarrays of nums with at most 2 elements are:

SubarrayMinimumMaximumSum
[1]112
[-3]-3-3-6
[1]112
[1, -3]-31-2
[-3, 1]-31-2
Final Total -6

The output would be -6.

Constraints:

  • 1 <= nums.length <= 80000
  • 1 <= k <= nums.length
  • -10^6 <= nums[i] <= 10^6

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public:
    long long minMaxSubarraySum(vector<int>& nums, int k) {
        deque<pair<int, int>> q;
        int n = nums.size();
        long long res = 0;
        long long cur = 0;
        // the question here is: for each element as the rightmost element,
        // the maximum number in the min(index + 1, k) subarrays
        // when we take in a new number, we check if it's the biggest number
        // in the last k numbers:
        // 1. if it is, then it would be the largest element for all subarrays
        // sized from 1 to k, push a (val, k) into the stk
        // 2. if it's not, then idx - prevIdx is the number of subarrays that it
        // is the largest element
        // 3. we add the val * num into cur, and we only need to add that value
        // into the res
        for (int i = 0; i < n; i++) {
            if (!q.empty()) {
                if (i >= k) {
                    q.front().second--;
                    cur -= nums[q.front().first];
                }
                if (q.front().first <= i - k) {
                    q.pop_front();
                }
            }
            while (!q.empty() && nums[i] > nums[q.back().first]) {
                cur -= (long long)nums[q.back().first] * q.back().second;
                q.pop_back();
            }
            if (q.empty()) {
                q.push_back({i, min(i + 1, k)});
            } else {
                int idx = q.back().first;
                q.push_back({i, i - idx});
            }
            cur += (long long)nums[q.back().first] * q.back().second;
            res += cur;
        }
        cout << res << endl;
        q.clear();
        cur = 0;
        for (int i = 0; i < n; i++) {
            if (!q.empty()) {
                if (i >= k) {
                    q.front().second--;
                    cur -= nums[q.front().first];
                }
                if (q.front().first <= i - k) {
                    q.pop_front();
                }
            }
            while (!q.empty() && nums[i] < nums[q.back().first]) {
                cur -= (long long)nums[q.back().first] * q.back().second;
                q.pop_back();
            }
            if (q.empty()) {
                q.push_back({i, min(i + 1, k)});
            } else {
                int idx = q.back().first;
                q.push_back({i, i - idx});
            }
            cur += (long long)nums[q.back().first] * q.back().second;
            res += cur;
        }
        return res;
    }
};