最大升序子数组和

标签: 数组

难度: Easy

给你一个正整数组成的数组 nums ，返回 nums 中一个 升序 子数组的最大可能元素和。

子数组是数组中的一个连续数字序列。

已知子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，若对所有 i（l <= i < r），numsi < numsi+1 都成立，则称这一子数组为 升序 子数组。注意，大小为 1 的子数组也视作 升序 子数组。

 

示例 1：

输入：nums = [10,20,30,5,10,50]
输出：65
解释：[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

Submission

运行时间: 18 ms

内存: 16.2 MB

from typing import List

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        max_sum = 0  # 最大元素和
        current_sum = nums[0]  # 当前元素和
        
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                current_sum += nums[i]
            else:
                max_sum = max(max_sum, current_sum)
                current_sum = nums[i]
        
        # 检查最后一个升序子数组的元素和
        max_sum = max(max_sum, current_sum)
        
        return max_sum

solution = Solution()
nums = [10, 20, 30, 5, 10, 50]
print(solution.maxAscendingSum(nums))  # 输出: 65

nums = [10, 20, 30, 40, 50]
print(solution.maxAscendingSum(nums))  # 输出: 150

nums = [12, 17, 15, 13, 10, 11, 12]
print(solution.maxAscendingSum(nums))  # 输出: 33

nums = [100, 10, 1]
print(solution.maxAscendingSum(nums))  # 输出: 100

Explain

此题解采用遍历一次数组的方法，通过一个循环检查每个元素是否大于前一个元素，以此判断是否继续属于当前的升序子数组。如果当前元素大于前一个元素，则将其加到当前子数组的和中（current_sum）；如果不是，则比较并更新最大子数组和（max_sum），并重新开始计算新的子数组的和。最后，循环结束后，再次更新最大子数组和，以确保最后一个升序子数组被考虑。

时间复杂度: O(n)

空间复杂度: O(1)

from typing import List

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        max_sum = 0  # 最大元素和
        current_sum = nums[0]  # 初始化当前元素和为数组的第一个元素
        
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                current_sum += nums[i]  # 当前元素大于前一个元素，累加到当前和
            else:
                max_sum = max(max_sum, current_sum)  # 更新最大元素和
                current_sum = nums[i]  # 重置当前元素和为当前元素
        
        # 循环结束后检查最后一个升序子数组的和
        max_sum = max(max_sum, current_sum)
        
        return max_sum

solution = Solution()
nums = [10, 20, 30, 5, 10, 50]
print(solution.maxAscendingSum(nums))  # 输出: 65

nums = [10, 20, 30, 40, 50]
print(solution.maxAscendingSum(nums))  # 输出: 150

nums = [12, 17, 15, 13, 10, 11, 12]
print(solution.maxAscendingSum(nums))  # 输出: 33

nums = [100, 10, 1]
print(solution.maxAscendingSum(nums))  # 输出: 100

Explore

在算法的循环中，current_sum 只有在遇到不满足升序条件的元素时才会与 max_sum 进行比较和可能的更新。如果数组的最后一个子数组是升序的，那么在循环结束时，这个升序子数组的和还没有与 max_sum 进行比较更新。因此，需要在循环结束后再进行一次比较，以确保包含数组末尾部分的升序子数组也被考虑进最大和中。

在算法中，当遇到一个元素不满足升序条件时，意味着前一个升序子数组已经结束，需要开始一个新的子数组。新子数组的起始元素就是当前的 nums[i]，因此 current_sum 需要重置为 nums[i]。如果从0开始，将无法正确计算新子数组的和，因为这会忽略掉当前这个元素的值。

如果数组中所有元素相等，那么每个元素都不会大于其前一个元素，因此算法中的 current_sum 将在每个元素处被重置为当前元素的值。最终，max_sum 将为单个元素的值，即元素的最大值。算法可以正确处理这种情况，虽然所有元素相同，但输出将是单个元素的值，这在逻辑上是一致的。

在当前的实现中，没有直接检查 nums 是否为空。如果 nums 为空，将在尝试访问 nums[0] 时抛出 IndexError 异常。为了优雅地处理这种情况，应该在函数开始时加入一个检查：如果 nums 为空，则直接返回 0。这样可以避免异常并正确处理空数组的情况。