5709. 最大升序子数组和

题目

给你一个正整数组成的数组 nums ，返回 nums 中一个 升序 子数组的最大可能元素和。
子数组是数组中的一个连续数字序列。
已知子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，若对所有 i（l <= i < r），numsi < numsi+1 都成立，则称这一子数组为 升序 子数组。注意，大小为 1 的子数组也视作 升序 子数组。
示例 1：

  1. 输入：nums = [10,20,30,5,10,50]
  2. 输出：65
  3. 解释：[5,10,50] 是元素和最大的升序子数组，最大元素和为 65 。

示例 2：

输入：nums = [10,20,30,40,50]
输出：150
解释：[10,20,30,40,50] 是元素和最大的升序子数组，最大元素和为 150 。

示例 3：

输入：nums = [12,17,15,13,10,11,12]
输出：33
解释：[10,11,12] 是元素和最大的升序子数组，最大元素和为 33 。

示例 4：

输入：nums = [100,10,1]
输出：100

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

题解

这是周赛的第一题，结果我一看题，好家伙，这不是最长上升子序列吗？
然后直接开始动规，唰唰唰一顿操作猛如虎，结果一提交直接傻眼。
原来这个子数组要求是连续的，我还以为是分散的，我还纳闷怎么第一题就开始动规了。。。
要求连续的话，就简单多了，折腾了半个小时😂

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        n=len(nums)
        S=[0]*n
        for i in range(n):
            for j in range(i,n):
                S[i]+=nums[j]
                if j==n-1 or nums[j+1]<=nums[j]:
                    break
        return max(S)

附上非连续情况的动规代码：

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        n=len(nums)
        S=[0]*n
        for i in range(n-1,0,-1):
            S[i]=nums[i]
            for j in range(i+1,n):
                if nums[j]>nums[i]:
                    S[i]=max(S[i],nums[i]+S[j])
        return max(S)