Hard

题目描述

给你一个下标从 0 开始的整数数组 nums。

你可以执行任意次操作，每次操作包括选择数组的一个子数组，并将其替换为该子数组元素的和。例如，给定数组 [1,3,5,6]，如果选择子数组 [3,5]，数组将变为 [1,8,6]。

返回应用操作后可以得到的非递减数组的最大长度。

子数组是数组中连续的非空元素序列。

示例 1：

输入：nums = [5,2,2]
输出：1
解释：长度为 3 的数组不是非递减的。
我们有两种方法使数组长度变为 2。
首先，选择子数组 [2,2] 将数组转换为 [5,4]。
其次，选择子数组 [5,2] 将数组转换为 [7,2]。
这两种方法得到的数组都不是非递减的。
如果我们选择子数组 [5,2,2] 并将其替换为 [9]，它就变成非递减的了。
所以答案是 1。

示例 2：

输入：nums = [1,2,3,4]
输出：4
解释：数组是非递减的。所以答案是 4。

示例 3：

输入：nums = [4,3,2,6]
输出：3
解释：将 [3,2] 替换为 [5] 将给定数组转换为 [4,5,6]，这是非递减的。
因为给定数组不是非递减的，所以最大可能答案是 3。

约束条件：

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

解题思路

解题思路

这是一道复杂的动态规划问题，核心思想是找到最优的合并策略来构造最长的非递减序列。

动态规划分析

定义 dp[i] 为处理前 i 个元素后能得到的最大非递减序列长度。同时需要记录每个状态对应的最后一个元素值。

关键观察：

  1. 对于位置 i，我们可以选择将 nums[j:i] 这段区间合并成一个元素，其值为这段区间的和
  2. 合并后的值必须 ≥ 前一段的最后元素值，才能保证非递减性
  3. 我们要在所有可行的 j 中选择使 dp[j] + 1 最大的方案

优化策略

朴素的动态规划是 O(n²) 的，需要优化：

  1. 单调队列优化：维护一个单调队列，队列中存储 (dp值, 对应的最后元素值, 前缀和) 的信息
  2. 前缀和：快速计算区间和
  3. 二分查找：在单调队列中快速找到满足条件的最优转移点

算法流程：

  1. 计算前缀和数组
  2. 维护单调队列，队列按 dp 值递增，最后元素值也递增
  3. 对每个位置 i，在队列中二分查找最大的满足条件的 dp 值
  4. 更新当前 dp 值，并将新状态加入队列，维护单调性

这种方法将复杂度降低到 O(n log n)。

代码实现

class Solution {
public:
    int findMaximumLength(vector<int>& nums) {
        int n = nums.size();
        vector<long long> prefix(n + 1);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        vector<int> dp(n + 1);
        vector<long long> last(n + 1);
        deque<pair<int, int>> dq; // (dp value, index)
        
        dq.push_back({0, 0});
        
        for (int i = 1; i <= n; i++) {
            // Find the best j such that prefix[i] - prefix[j] >= last[j]
            int left = 0, right = dq.size() - 1, best = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                int j = dq[mid].second;
                if (prefix[i] - prefix[j] >= last[j]) {
                    best = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            if (best != -1) {
                int j = dq[best].second;
                dp[i] = dp[j] + 1;
                last[i] = prefix[i] - prefix[j];
            } else {
                dp[i] = 1;
                last[i] = prefix[i];
            }
            
            // Maintain monotonic deque
            while (!dq.empty() && (dq.back().first < dp[i] || 
                   (dq.back().first == dp[i] && last[dq.back().second] >= last[i]))) {
                dq.pop_back();
            }
            dq.push_back({dp[i], i});
        }
        
        return dp[n];
    }
};

class Solution:
    def findMaximumLength(self, nums: List[int]) -> int:
        from collections import deque
        import bisect
        
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        dp = [0] * (n + 1)
        last = [0] * (n + 1)
        dq = deque([(0, 0)])  # (dp value, index)
        
        for i in range(1, n + 1):
            # Binary search for the best j
            left, right = 0, len(dq) - 1
            best = -1
            while left <= right:
                mid = (left + right) // 2
                j = dq[mid][1]
                if prefix[i] - prefix[j] >= last[j]:
                    best = mid
                    left = mid + 1
                else:
                    right = mid - 1
            
            if best != -1:
                j = dq[best][1]
                dp[i] = dp[j] + 1
                last[i] = prefix[i] - prefix[j]
            else:
                dp[i] = 1
                last[i] = prefix[i]
            
            # Maintain monotonic deque
            while dq and (dq[-1][0] < dp[i] or 
                         (dq[-1][0] == dp[i] and last[dq[-1][1]] >= last[i])):
                dq.pop()
            dq.append((dp[i], i))
        
        return dp[n]

public class Solution {
    public int FindMaximumLength(int[] nums) {
        int n = nums.Length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        int[] dp = new int[n + 1];
        long[] last = new long[n + 1];
        var dq = new List<(int dp, int index)>();
        
        dq.Add((0, 0));
        
        for (int i = 1; i <= n; i++) {
            // Binary search for the best j
            int left = 0, right = dq.Count - 1, best = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                int j = dq[mid].index;
                if (prefix[i] - prefix[j] >= last[j]) {
                    best = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            if (best != -1) {
                int j = dq[best].index;
                dp[i] = dp[j] + 1;
                last[i] = prefix[i] - prefix[j];
            } else {
                dp[i] = 1;
                last[i] = prefix[i];
            }
            
            // Maintain monotonic deque
            while (dq.Count > 0 && (dq[dq.Count - 1].dp < dp[i] || 
                   (dq[dq.Count - 1].dp == dp[i] && last[dq[dq.Count - 1].index] >= last[i]))) {
                dq.RemoveAt(dq.Count - 1);
            }
            dq.Add((dp[i], i));
        }
        
        return dp[n];
    }
}

var findMaximumLength = function(nums) {
    const n = nums.length;
    const prefixSum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }
    
    const dp = new Array(n + 1).fill(0);
    const last = new Array(n + 1).fill(0);
    
    let j = 0;
    for (let i = 1; i <= n; i++) {
        while (j < i && prefixSum[i] - prefixSum[j] >= last[j]) {
            if (dp[j] + 1 > dp[i] || (dp[j] + 1 === dp[i] && prefixSum[i] - prefixSum[j] < last[i])) {
                dp[i] = dp[j] + 1;
                last[i] = prefixSum[i] - prefixSum[j];
            }
            j++;
        }
        if (dp[i] === 0) {
            dp[i] = dp[i - 1];
            last[i] = last[i - 1];
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n log n)，其中 n 是数组长度。每个位置最多进出单调队列一次，每次二分查找的复杂度是 O(log n)
空间复杂度O(n)，需要存储前缀和数组、dp 数组、last 数组和单调队列