Easy

题目描述

给你一个正整数数组 nums ，返回 nums 中一个 严格递增子数组 的最大可能元素和。

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

示例 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 。

提示：

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

解题思路

这道题要求找到严格递增子数组的最大和。我们可以使用一次遍历的方法来解决：

核心思路：

  1. 遍历数组，维护当前升序子数组的和
  2. 当遇到比前一个元素小或相等的元素时，当前升序子数组结束
  3. 更新最大和，然后重新开始计算新的升序子数组

具体步骤：

  • 使用 currentSum 记录当前升序子数组的和
  • 使用 maxSum 记录所有升序子数组中的最大和
  • 遍历数组时，如果当前元素大于前一个元素，则继续累加；否则重新开始计算

时间复杂度分析： 只需要一次遍历，所以时间复杂度为 O(n) 空间复杂度分析： 只使用了常数额外空间，所以空间复杂度为 O(1)

这种贪心的方法是最优解，因为我们可以在一次遍历中找到所有可能的升序子数组并计算它们的和。

代码实现

class Solution {
public:
    int maxAscendingSum(vector<int>& nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i-1]) {
                currentSum += nums[i];
            } else {
                maxSum = max(maxSum, currentSum);
                currentSum = nums[i];
            }
        }
        
        return max(maxSum, currentSum);
    }
};

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        max_sum = nums[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]
        
        return max(max_sum, current_sum)

public class Solution {
    public int MaxAscendingSum(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] > nums[i-1]) {
                currentSum += nums[i];
            } else {
                maxSum = Math.Max(maxSum, currentSum);
                currentSum = nums[i];
            }
        }
        
        return Math.Max(maxSum, currentSum);
    }
}

var maxAscendingSum = function(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i-1]) {
            currentSum += nums[i];
        } else {
            maxSum = Math.max(maxSum, currentSum);
            currentSum = nums[i];
        }
    }
    
    return Math.max(maxSum, currentSum);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组一次
空间复杂度O(1)只使用了常数额外空间

相关题目