Medium

题目描述

给你一个长度为 n 的整数数组 nums。

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

cost(l, r) = nums[l] - nums[l + 1] + … + nums[r] * (-1)^(r - l)

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

正式地，如果 nums 被分割成 k 个子数组（k > 1），分割点为索引 i1, i2, …, ik-1（其中 0 <= i1 < i2 < … < ik-1 < n-1），那么总成本为：

cost(0, i1) + cost(i1 + 1, i2) + … + cost(ik-1 + 1, n - 1)

返回一个整数，表示在最优分割数组后子数组的最大总成本。

注意：如果 nums 不被分割成子数组（即 k = 1），总成本就是 cost(0, n - 1)。

示例 1：

输入：nums = [1,-2,3,4]
输出：10
解释：
一种最大化总成本的方法是将 [1, -2, 3, 4] 分割为子数组 [1, -2, 3] 和 [4]。
总成本为 (1 + 2 + 3) + 4 = 10。

示例 2：

输入：nums = [1,-1,1,-1]
输出：4
解释：
一种最大化总成本的方法是将 [1, -1, 1, -1] 分割为子数组 [1, -1] 和 [1, -1]。
总成本为 (1 + 1) + (1 + 1) = 4。

示例 3：

输入：nums = [0]
输出：0
解释：
无法进一步分割数组，所以答案是 0。

示例 4：

输入：nums = [1,-1]
输出：2
解释：
选择整个数组得到总成本 1 + 1 = 2，这是最大值。

约束条件：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

解题思路

这道题本质上是一个动态规划问题。关键观察是：对于子数组中的每个元素，其符号是交替的，第一个元素为正，第二个为负，第三个为正，依此类推。

思路分析：

  1. 问题转换：由于我们可以在任何位置开始新的子数组，这个问题等价于在数组中选择一些元素并将其符号翻转为负数来最大化总和。但有两个限制：

    • 不能连续翻转两个相邻元素的符号
    • 数组的第一个元素不能为负数

  2. 状态定义：使用动态规划，定义 dp[i][0] 和 dp[i][1]：

    • dp[i][0]：前 i+1 个元素中，第 i 个元素符号未翻转时的最大和
    • dp[i][1]：前 i+1 个元素中，第 i 个元素符号翻转时的最大和

  3. 状态转移：

    • dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + nums[i]
    • dp[i][1] = dp[i-1][0] - nums[i]

  4. 初始状态：

    • 只有一个元素时：dp[0][0] = nums[0]，dp[0][1] = -∞（第一个元素不能翻转）
    • 有两个元素时：dp[1][0] = nums[0] + nums[1]，dp[1][1] = nums[0] - nums[1]

  5. 空间优化：由于每个状态只依赖前一个状态，可以用两个变量来优化空间复杂度。

代码实现

class Solution {
public:
    long long maximumTotalCost(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        
        long long dp0 = nums[0] + nums[1];  // dp[i][0]
        long long dp1 = nums[0] - nums[1];  // dp[i][1]
        
        for (int i = 2; i < n; i++) {
            long long newDp0 = max(dp0, dp1) + nums[i];
            long long newDp1 = dp0 - nums[i];
            dp0 = newDp0;
            dp1 = newDp1;
        }
        
        return max(dp0, dp1);
    }
};

class Solution:
    def maximumTotalCost(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        
        dp0 = nums[0] + nums[1]  # dp[i][0]
        dp1 = nums[0] - nums[1]  # dp[i][1]
        
        for i in range(2, n):
            new_dp0 = max(dp0, dp1) + nums[i]
            new_dp1 = dp0 - nums[i]
            dp0, dp1 = new_dp0, new_dp1
        
        return max(dp0, dp1)

public class Solution {
    public long MaximumTotalCost(int[] nums) {
        int n = nums.Length;
        if (n == 1) return nums[0];
        
        long dp0 = nums[0] + nums[1];  // dp[i][0]
        long dp1 = nums[0] - nums[1];  // dp[i][1]
        
        for (int i = 2; i < n; i++) {
            long newDp0 = Math.Max(dp0, dp1) + nums[i];
            long newDp1 = dp0 - nums[i];
            dp0 = newDp0;
            dp1 = newDp1;
        }
        
        return Math.Max(dp0, dp1);
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumTotalCost = function(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];
    
    // dp[i][0] = max cost ending at index i with nums[i] having positive sign
    // dp[i][1] = max cost ending at index i with nums[i] having negative sign
    let dp = Array(n).fill().map(() => [0, 0]);
    
    dp[0][0] = nums[0];
    dp[0][1] = -Infinity;
    
    for (let i = 1; i < n; i++) {
        // Case 1: nums[i] has positive sign (start of new subarray)
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]) + nums[i];
        
        // Case 2: nums[i] has negative sign (continue current subarray)
        dp[i][1] = dp[i-1][0] - nums[i];
    }
    
    return Math.max(dp[n-1][0], dp[n-1][1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)遍历数组一次，每个元素进行常数时间操作
空间复杂度O(1)只使用常数个变量存储状态