mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
62 lines
2.8 KiB
HTML
62 lines
2.8 KiB
HTML
<p>You are given an array of integers <code>nums</code> with length <code>n</code>, and a positive <strong>odd</strong> integer <code>k</code>.</p>
|
|
|
|
<p>Select exactly <b><code>k</code></b> disjoint <span data-keyword="subarray-nonempty">subarrays</span> <b><code>sub<sub>1</sub>, sub<sub>2</sub>, ..., sub<sub>k</sub></code></b> from <code>nums</code> such that the last element of <code>sub<sub>i</sub></code> appears before the first element of <code>sub<sub>{i+1}</sub></code> for all <code>1 <= i <= k-1</code>. The goal is to maximize their combined strength.</p>
|
|
|
|
<p>The strength of the selected subarrays is defined as:</p>
|
|
|
|
<p><code>strength = k * sum(sub<sub>1</sub>)- (k - 1) * sum(sub<sub>2</sub>) + (k - 2) * sum(sub<sub>3</sub>) - ... - 2 * sum(sub<sub>{k-1}</sub>) + sum(sub<sub>k</sub>)</code></p>
|
|
|
|
<p>where <b><code>sum(sub<sub>i</sub>)</code></b> is the sum of the elements in the <code>i</code>-th subarray.</p>
|
|
|
|
<p>Return the <strong>maximum</strong> possible strength that can be obtained from selecting exactly <b><code>k</code></b> disjoint subarrays from <code>nums</code>.</p>
|
|
|
|
<p><strong>Note</strong> that the chosen subarrays <strong>don't</strong> need to cover the entire array.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,-1,2], k = 3</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">22</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>The best possible way to select 3 subarrays is: nums[0..2], nums[3..3], and nums[4..4]. The strength is calculated as follows:</p>
|
|
|
|
<p><code>strength = 3 * (1 + 2 + 3) - 2 * (-1) + 2 = 22</code></p>
|
|
|
|
<p> </p>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [12,-2,-2,-2,-2], k = 5</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">64</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>The only possible way to select 5 disjoint subarrays is: nums[0..0], nums[1..1], nums[2..2], nums[3..3], and nums[4..4]. The strength is calculated as follows:</p>
|
|
|
|
<p><code>strength = 5 * 12 - 4 * (-2) + 3 * (-2) - 2 * (-2) + (-2) = 64</code></p>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [-1,-2,-3], k = </span>1</p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">-1</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>The best possible way to select 1 subarray is: nums[0..0]. The strength is -1.</p>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= n <= 10<sup>4</sup></code></li>
|
|
<li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li>
|
|
<li><code>1 <= k <= n</code></li>
|
|
<li><code>1 <= n * k <= 10<sup>6</sup></code></li>
|
|
<li><code>k</code> is odd.</li>
|
|
</ul>
|