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

你可以在数组上执行下述操作 任意 次：

  • 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的 最大 元素的值。

 

示例 1：

输入：nums = [2,3,7,9,3]
输出：21
解释：我们可以在数组上执行下述操作：
- 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
- 选中 i = 1 ，得到数组 nums = [5,16,3] 。
- 选中 i = 0 ，得到数组 nums = [21,3] 。
最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

示例 2：

输入：nums = [5,3,3]
输出：11
解释：我们可以在数组上执行下述操作：
- 选中 i = 1 ，得到数组 nums = [5,6] 。
- 选中 i = 0 ，得到数组 nums = [11] 。
最终数组中只有一个元素，即 11 。

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106

思路分析

倒序即可，如果是仅有1个数，不进入循环，则需要统计nums中最大值
时间复杂度 O()

比赛ac代码

1
2
3
4
5
6
7
8
class Solution:
    def maxArrayValue(self, nums: List[int]) -> int:
        r = len(nums) - 1
        while r > 0: 
            if nums[r] >= nums[r-1]:
                nums[r-1]+=nums[r]
            r-=1
        return max(nums)

小羊肖恩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxArrayValue(self, nums: List[int]) -> int:
        n = len(nums)
        pt = n - 1
        ans = 0
        while pt >= 0:
            res = nums[pt]
            pt -= 1
            # 找每个结束点最多能走到哪个开始的节点
            while pt >= 0 and nums[pt] <= res:
                res += nums[pt]
                pt -= 1
            # 下一次直接避开这个子数组里面的每一个数
            ans = max(ans, res)
        return ans

雪景式

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxArrayValue(self, nums: List[int]) -> int:
        n = len(nums)
        ans = nums[-1]
        count = nums[-1]
        for i in range(n - 2,-1,-1):
            if nums[i] <= count:
                count += nums[i]
                ans = max(ans,count)
            else:
                count = nums[i]
                ans = max(ans,count)
        return ans