Hard

题目描述

给你一个长度为 n 的整数数组 nums 和一个正奇数 k。

从 nums 中选择恰好 k 个不相交的子数组 sub1, sub2, ..., subk，使得对于所有 1 <= i <= k-1，subi 的最后一个元素出现在 sub{i+1} 的第一个元素之前。目标是最大化它们的组合强度。

所选子数组的强度定义为：

strength = k * sum(sub1) - (k - 1) * sum(sub2) + (k - 2) * sum(sub3) - ... - 2 * sum(sub{k-1}) + sum(subk)

其中 sum(subi) 是第 i 个子数组中元素的和。

返回从 nums 中选择恰好 k 个不相交子数组可以获得的最大可能强度。

注意选择的子数组不需要覆盖整个数组。

示例 1：

输入：nums = [1,2,3,-1,2], k = 3
输出：22
解释：选择3个子数组的最佳方式是：nums[0..2], nums[3..3], 和 nums[4..4]。
强度计算如下：strength = 3 * (1 + 2 + 3) - 2 * (-1) + 2 = 22

示例 2：

输入：nums = [12,-2,-2,-2,-2], k = 5
输出：64
解释：选择5个不相交子数组的唯一方式是：nums[0..0], nums[1..1], nums[2..2], nums[3..3], 和 nums[4..4]。
强度计算如下：strength = 5 * 12 - 4 * (-2) + 3 * (-2) - 2 * (-2) + (-2) = 64

示例 3：

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：选择1个子数组的最佳方式是：nums[0..0]。强度为-1。

提示：

  • 1 <= n <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • 1 <= k <= n
  • 1 <= n * k <= 10^6
  • k 是奇数

解题思路

这是一道复杂的动态规划题目，需要仔细分析状态转移。

核心思路：

观察强度公式，第 i 个子数组的系数为 k - (i-1)，当 i 为奇数时系数为正，为偶数时系数为负。这启发我们用动态规划来解决。

状态定义：

  • dp[i][j][flag] 表示从位置 i 开始，选择 j 个子数组能获得的最大强度
  • flag = 0 表示当前位置不在任何子数组中
  • flag = 1 表示当前位置在某个子数组中

状态转移：

  1. 对于 dp[i][j][0]（不在子数组中）：

    • 可以跳过当前元素：dp[i+1][j][0]
    • 可以从当前位置开始新子数组：dp[i][j][1]

  2. 对于 dp[i][j][1]（在子数组中）：

    • 当前元素的贡献为 nums[i] * coeff(j)，其中 coeff(j) = j （奇数为正，偶数为负）
    • 可以继续当前子数组：dp[i+1][j][1]
    • 可以结束当前子数组：dp[i+1][j-1][0]

边界条件：

  • dp[n][0][0] = 0（选择0个子数组，强度为0）
  • 其他状态初始化为负无穷

优化： 由于状态空间较大，我们使用记忆化递归来避免重复计算。

代码实现

class Solution {
public:
    long long maximumStrength(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<vector<long long>>> memo(n + 1, vector<vector<long long>>(k + 1, vector<long long>(2, LLONG_MIN)));
        
        function<long long(int, int, int)> dfs = [&](int i, int j, int flag) -> long long {
            if (j == 0) return flag == 0 ? 0 : LLONG_MIN;
            if (i == n) return LLONG_MIN;
            if (memo[i][j][flag] != LLONG_MIN) return memo[i][j][flag];
            
            long long res = LLONG_MIN;
            if (flag == 0) {
                res = max(res, dfs(i + 1, j, 0));
                res = max(res, dfs(i, j, 1));
            } else {
                long long coeff = (j % 2 == 1) ? j : -j;
                long long cont = dfs(i + 1, j, 1);
                long long end = dfs(i + 1, j - 1, 0);
                if (cont != LLONG_MIN) res = max(res, nums[i] * coeff + cont);
                if (end != LLONG_MIN) res = max(res, nums[i] * coeff + end);
            }
            return memo[i][j][flag] = res;
        };
        
        return dfs(0, k, 0);
    }
};

class Solution:
    def maximumStrength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        @lru_cache(None)
        def dfs(i, j, flag):
            if j == 0:
                return 0 if flag == 0 else float('-inf')
            if i == n:
                return float('-inf')
            
            if flag == 0:
                return max(dfs(i + 1, j, 0), dfs(i, j, 1))
            else:
                coeff = j if j % 2 == 1 else -j
                cont = dfs(i + 1, j, 1)
                end = dfs(i + 1, j - 1, 0)
                res = float('-inf')
                if cont != float('-inf'):
                    res = max(res, nums[i] * coeff + cont)
                if end != float('-inf'):
                    res = max(res, nums[i] * coeff + end)
                return res
        
        return dfs(0, k, 0)

public class Solution {
    private long[,,] memo;
    private int[] nums;
    private int n;
    
    public long MaximumStrength(int[] nums, int k) {
        this.nums = nums;
        this.n = nums.Length;
        memo = new long[n + 1, k + 1, 2];
        
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= k; j++)
                for (int f = 0; f < 2; f++)
                    memo[i, j, f] = long.MinValue;
        
        return Dfs(0, k, 0);
    }
    
    private long Dfs(int i, int j, int flag) {
        if (j == 0) return flag == 0 ? 0 : long.MinValue;
        if (i == n) return long.MinValue;
        if (memo[i, j, flag] != long.MinValue) return memo[i, j, flag];
        
        long res = long.MinValue;
        if (flag == 0) {
            res = Math.Max(res, Dfs(i + 1, j, 0));
            res = Math.Max(res, Dfs(i, j, 1));
        } else {
            long coeff = (j % 2 == 1) ? j : -j;
            long cont = Dfs(i + 1, j, 1);
            long end = Dfs(i + 1, j - 1, 0);
            if (cont != long.MinValue) res = Math.Max(res, (long)nums[i] * coeff + cont);
            if (end != long.MinValue) res = Math.Max(res, (long)nums[i] * coeff + end);
        }
        return memo[i, j, flag] = res;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumStrength = function(nums, k) {
    const n = nums.length;
    const dp = Array(n + 1).fill(null).map(() => Array(k + 1).fill(-Infinity));
    const best = Array(n + 1).fill(null).map(() => Array(k + 1).fill(-Infinity));
    
    dp[0][0] = 0;
    best[0][0] = 0;
    
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= Math.min(i, k); j++) {
            dp[i][j] = best[i-1][j];
            
            if (j > 0) {
                const coeff = k - j + 1;
                const sign = (j - 1) % 2 === 0 ? 1 : -1;
                const multiplier = sign * coeff;
                
                let sum = 0;
                for (let start = i - 1; start >= j - 1; start--) {
                    sum += nums[start];
                    if (best[start][j-1] !== -Infinity) {
                        dp[i][j] = Math.max(dp[i][j], best[start][j-1] + multiplier * sum);
                    }
                }
            }
            
            best[i][j] = Math.max(best[i-1][j], dp[i][j]);
        }
    }
    
    return best[n][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × k × 2) = O(nk)
空间复杂度O(n × k × 2) = O(nk)

相关题目