maximize-total-cost-of-alternating-subarrays

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>nums</code> with length <code>n</code>.

The cost of a subarray <code>nums[l..r]</code>, where <code>0 &lt;= l &lt;= r &lt; n</code>, is defined as:

<code>cost(l, r) = nums[l] - nums[l + 1] + ... + nums[r] * (&minus;1)r &minus; l</code>

Your task is to split <code>nums</code> into subarrays such that the total cost of the subarrays is maximized, ensuring each element belongs to exactly one subarray.

Formally, if <code>nums</code> is split into <code>k</code> subarrays, where <code>k &gt; 1</code>, at indices <code>i1, i2, ..., ik &minus; 1</code>, where <code>0 &lt;= i1 &lt; i2 &lt; ... &lt; ik - 1 &lt; n - 1</code>, then the total cost will be:

<code>cost(0, i1) + cost(i1 + 1, i2) + ... + cost(ik &minus; 1 + 1, n &minus; 1)</code>

Return an integer denoting the maximum total cost of the subarrays after splitting the array optimally.

Note: If <code>nums</code> is not split into subarrays, i.e. <code>k = 1</code>, the total cost is simply <code>cost(0, n - 1)</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,-2,3,4]

Output: 10

Explanation:

One way to maximize the total cost is by splitting <code>[1, -2, 3, 4]</code> into subarrays <code>[1, -2, 3]</code> and <code>[4]</code>. The total cost will be <code>(1 + 2 + 3) + 4 = 10</code>.
</div>

Example 2:

<div class="example-block">
Input: nums = [1,-1,1,-1]

Output: 4

Explanation:

One way to maximize the total cost is by splitting <code>[1, -1, 1, -1]</code> into subarrays <code>[1, -1]</code> and <code>[1, -1]</code>. The total cost will be <code>(1 + 1) + (1 + 1) = 4</code>.
</div>

Example 3:

<div class="example-block">
Input: nums = [0]

Output: 0

Explanation:

We cannot split the array further, so the answer is 0.
</div>

Example 4:

<div class="example-block">
Input: nums = [1,-1]

Output: 2

Explanation:

Selecting the whole array gives a total cost of <code>1 + 1 = 2</code>, which is the maximum.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>-109 &lt;= nums[i] &lt;= 109</code></li>
</ul>

maximumTotalCost

Maximize Total Cost of Alternating Subarrays

Array

Dynamic Programming

给你一个长度为 <code>n</code> 的整数数组 <code>nums</code>。

子数组 <code>nums[l..r]</code>（其中 <code>0 &lt;= l &lt;= r &lt; n</code>）的 成本 定义为：

<code>cost(l, r) = nums[l] - nums[l + 1] + ... + nums[r] * (−1)r − l</code>

你的任务是将 <code>nums</code> 分割成若干子数组，使得所有子数组的成本之和 最大化，并确保每个元素 正好 属于一个子数组。

具体来说，如果 <code>nums</code> 被分割成 <code>k</code> 个子数组，且分割点为索引 <code>i1, i2, ..., ik − 1</code>（其中 <code>0 &lt;= i1 &lt; i2 &lt; ... &lt; ik - 1 &lt; n - 1</code>），则总成本为：

<code>cost(0, i1) + cost(i1 + 1, i2) + ... + cost(ik − 1 + 1, n − 1)</code>

返回在最优分割方式下的子数组成本之和的最大值。

注意：如果 <code>nums</code> 没有被分割，即 <code>k = 1</code>，则总成本即为 <code>cost(0, n - 1)</code>。

&nbsp;

示例 1：

<div class="example-block">
输入： nums = [1,-2,3,4]

输出： 10

解释：

一种总成本最大化的方法是将 <code>[1, -2, 3, 4]</code> 分割成子数组 <code>[1, -2, 3]</code> 和 <code>[4]</code>。总成本为 <code>(1 + 2 + 3) + 4 = 10</code>。
</div>

示例 2：

<div class="example-block">
输入： nums = [1,-1,1,-1]

输出： 4

解释：

一种总成本最大化的方法是将 <code>[1, -1, 1, -1]</code> 分割成子数组 <code>[1, -1]</code> 和 <code>[1, -1]</code>。总成本为 <code>(1 + 1) + (1 + 1) = 4</code>。
</div>

示例 3：

<div class="example-block">
输入： nums = [0]

输出： 0

解释：

无法进一步分割数组，因此答案为 0。
</div>

示例 4：

<div class="example-block">
输入： nums = [1,-1]

输出： 2

解释：

选择整个数组，总成本为 <code>1 + 1 = 2</code>，这是可能的最大成本。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>-109 &lt;= nums[i] &lt;= 109</code></li>
</ul>