3430. Maximum and Minimum Sums of at Most Size K Subarrays Hard
1/**
2 * [3430] Maximum and Minimum Sums of at Most Size K Subarrays
3 *
4 * You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all <span data-keyword="subarray-nonempty">subarrays</span> with at most k elements.
5 *
6 * <strong class="example">Example 1:
7 * <div class="example-block">
8 * Input: <span class="example-io">nums = [1,2,3], k = 2</span>
9 * Output: <span class="example-io">20</span>
10 * Explanation:
11 * The subarrays of nums with at most 2 elements are:
12 * <table style="border: 1px solid black;">
13 * <tbody>
14 * <tr>
15 * <th style="border: 1px solid black;">Subarray</th>
16 * <th style="border: 1px solid black;">Minimum</th>
17 * <th style="border: 1px solid black;">Maximum</th>
18 * <th style="border: 1px solid black;">Sum</th>
19 * </tr>
20 * <tr>
21 * <td style="border: 1px solid black;">[1]</td>
22 * <td style="border: 1px solid black;">1</td>
23 * <td style="border: 1px solid black;">1</td>
24 * <td style="border: 1px solid black;">2</td>
25 * </tr>
26 * <tr>
27 * <td style="border: 1px solid black;">[2]</td>
28 * <td style="border: 1px solid black;">2</td>
29 * <td style="border: 1px solid black;">2</td>
30 * <td style="border: 1px solid black;">4</td>
31 * </tr>
32 * <tr>
33 * <td style="border: 1px solid black;">[3]</td>
34 * <td style="border: 1px solid black;">3</td>
35 * <td style="border: 1px solid black;">3</td>
36 * <td style="border: 1px solid black;">6</td>
37 * </tr>
38 * <tr>
39 * <td style="border: 1px solid black;">[1, 2]</td>
40 * <td style="border: 1px solid black;">1</td>
41 * <td style="border: 1px solid black;">2</td>
42 * <td style="border: 1px solid black;">3</td>
43 * </tr>
44 * <tr>
45 * <td style="border: 1px solid black;">[2, 3]</td>
46 * <td style="border: 1px solid black;">2</td>
47 * <td style="border: 1px solid black;">3</td>
48 * <td style="border: 1px solid black;">5</td>
49 * </tr>
50 * <tr>
51 * <td style="border: 1px solid black;">Final Total</td>
52 * <td style="border: 1px solid black;"> </td>
53 * <td style="border: 1px solid black;"> </td>
54 * <td style="border: 1px solid black;">20</td>
55 * </tr>
56 * </tbody>
57 * </table>
58 * The output would be 20.
59 * </div>
60 * <strong class="example">Example 2:
61 * <div class="example-block">
62 * Input: <span class="example-io">nums = [1,-3,1], k = 2</span>
63 * Output: <span class="example-io">-6</span>
64 * Explanation:
65 * The subarrays of nums with at most 2 elements are:
66 * <table style="border: 1px solid black;">
67 * <tbody>
68 * <tr>
69 * <th style="border: 1px solid black;">Subarray</th>
70 * <th style="border: 1px solid black;">Minimum</th>
71 * <th style="border: 1px solid black;">Maximum</th>
72 * <th style="border: 1px solid black;">Sum</th>
73 * </tr>
74 * <tr>
75 * <td style="border: 1px solid black;">[1]</td>
76 * <td style="border: 1px solid black;">1</td>
77 * <td style="border: 1px solid black;">1</td>
78 * <td style="border: 1px solid black;">2</td>
79 * </tr>
80 * <tr>
81 * <td style="border: 1px solid black;">[-3]</td>
82 * <td style="border: 1px solid black;">-3</td>
83 * <td style="border: 1px solid black;">-3</td>
84 * <td style="border: 1px solid black;">-6</td>
85 * </tr>
86 * <tr>
87 * <td style="border: 1px solid black;">[1]</td>
88 * <td style="border: 1px solid black;">1</td>
89 * <td style="border: 1px solid black;">1</td>
90 * <td style="border: 1px solid black;">2</td>
91 * </tr>
92 * <tr>
93 * <td style="border: 1px solid black;">[1, -3]</td>
94 * <td style="border: 1px solid black;">-3</td>
95 * <td style="border: 1px solid black;">1</td>
96 * <td style="border: 1px solid black;">-2</td>
97 * </tr>
98 * <tr>
99 * <td style="border: 1px solid black;">[-3, 1]</td>
100 * <td style="border: 1px solid black;">-3</td>
101 * <td style="border: 1px solid black;">1</td>
102 * <td style="border: 1px solid black;">-2</td>
103 * </tr>
104 * <tr>
105 * <td style="border: 1px solid black;">Final Total</td>
106 * <td style="border: 1px solid black;"> </td>
107 * <td style="border: 1px solid black;"> </td>
108 * <td style="border: 1px solid black;">-6</td>
109 * </tr>
110 * </tbody>
111 * </table>
112 * The output would be -6.
113 * </div>
114 *
115 * Constraints:
116 *
117 * 1 <= nums.length <= 80000
118 * 1 <= k <= nums.length
119 * -10^6 <= nums[i] <= 10^6
120 *
121 */
122pub struct Solution {}
123
124// problem: https://leetcode.com/problems/maximum-and-minimum-sums-of-at-most-size-k-subarrays/
125// discuss: https://leetcode.com/problems/maximum-and-minimum-sums-of-at-most-size-k-subarrays/discuss/?currentPage=1&orderBy=most_votes&query=
126
127// submission codes start here
128
129impl Solution {
130 pub fn min_max_subarray_sum(nums: Vec<i32>, k: i32) -> i64 {
131
132 }
133}
134
135// submission codes end
136
137#[cfg(test)]
138mod tests {
139 use super::*;
140
141 #[test]
142 fn test_3430() {
143 }
144}
145Back
© 2025 bowen.ge All Rights Reserved.