2025-10-10：非递减数组的最大长度。用go语言，给定一个整数数组。每次操作可以选取数组中一段连续的元素，把这一段合并成一个元素，合并后这个新元素的值等于被合并那一段里的最大数。可以重复进行这种合并（也可以一次也不做），但最终得到的序列必须满足每个元素都不少于它前面的元素（即不下降）。求在满足这一条件的前提下，最终数组能达到的最大长度。

1 <= nums.length <= 200000。

1 <= nums[i] <= 200000。

输入： nums = [4,2,5,3,5]。

输出： 3。

解释：

实现最大长度的一种方法是：

将子数组 nums[1…2] = [2, 5] 替换为 5 → [4, 5, 3, 5]。

将子数组 nums[2…3] = [3, 5] 替换为 5 → [4, 5, 5]。

最终数组 [4, 5, 5] 是非递减的，长度为 3。

题目来自力扣3523。

解决过程

该问题可以通过一种贪心算法来解决，具体步骤如下：

1. 初始化：设置当前最大值 mx 为 0（因为数组元素均为正整数），设置计数器 ans 为 0，用于记录最终序列的长度。

2. 遍历数组：从左到右依次处理每个元素 x：

   • 如果 x 大于或等于当前最大值 mx，则说明 x 可以作为一个独立段保留在最终序列中，不会破坏非递减性。此时，增加计数器 ans，并更新 mx 为 x。
   • 如果 x 小于当前最大值 mx，则说明 x 不能作为独立段保留，必须被合并到之前的某个段中（不会增加最终序列的长度），因此跳过该元素。

3. 返回结果：遍历结束后，计数器 ans 的值即为最终非递减数组的最大可能长度。

这种算法的核心思想是：通过维护当前最大值，确保每次遇到不小于当前最大值的元素时，都能增加一个独立段，从而最大化段的数量。这些段的最大值序列自然形成非递减顺序，因此不需要显式进行合并操作，只需计数即可。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。算法只需遍历数组一次，每个元素处理时间为常数。
• 空间复杂度：O(1)。算法只使用了固定数量的额外变量（如 mx 和 ans），与输入规模无关。

Go完整代码如下：

package main

import (
	"fmt"
)

func maximumPossibleSize(nums []int) (ans int) {
	mx := 0
	for _, x := range nums {
		if x >= mx {
			mx = x
			ans++
		}
	}
	return
}

func main() {
	nums := []int{4, 2, 5, 3, 5}
	result := maximumPossibleSize(nums)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def maximumPossibleSize(nums):
    ans = 0
    mx = 0
    for x in nums:
        if x >= mx:
            mx = x
            ans += 1
    return ans

if __name__ == "__main__":
    nums = [4, 2, 5, 3, 5]
    result = maximumPossibleSize(nums)
    print(result)