1800. 最大升序子数组和

🟢   🔖  数组  🔗 力扣 LeetCode

题目

Given an array of positive integers nums, return the _maximum possible sum of anascending subarray in _nums.

A subarray is defined as a contiguous sequence of numbers in an array.

A subarray [numsl, numsl+1, ..., numsr-1, numsr] is ascending if for all i where l <= i < r, numsi < numsi+1. Note that a subarray of size 1 is ascending.

Example 1:

Input: nums = [10,20,30,5,10,50]

Output: 65

Explanation:[5,10,50] is the ascending subarray with the maximum sum of 65.

Example 2:

Input: nums = [10,20,30,40,50]

Output: 150

Explanation:[10,20,30,40,50] is the ascending subarray with the maximum sum of 150.

Example 3:

Input: nums = [12,17,15,13,10,11,12]

Output: 33

Explanation:[10,11,12] is the ascending subarray with the maximum sum of 33.

Constraints:

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

题目大意

给你一个正整数组成的数组 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

解题思路

1. 初始化 sum 和 maxSum 为数组的第一个元素。

2. 遍历数组，从第二个元素开始：

   • 如果当前元素大于前一个元素，说明当前递增子数组还在继续，累加当前元素到 sum。
   • 如果当前元素不大于前一个元素，说明递增子数组结束了，更新 maxSum 为当前的 sum，然后重置 sum 为当前元素。

3. 遍历完成后，我们需要再返回一次 maxSum 或 sum 中的较大值，确保计算包括最后一个递增子数组。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度，遍历数组一次。
• 空间复杂度：O(1)，只使用常数空间来存储 sum 和 maxSum。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAscendingSum = function (nums) {
	let sum = nums[0],
		maxSum = nums[0];
	for (let i = 1; i < nums.length; i++) {
		if (nums[i] > nums[i - 1]) {
			sum += nums[i];
		} else {
			maxSum = Math.max(maxSum, sum);
			sum = nums[i];
		}
	}
	return Math.max(maxSum, sum);
};

相关题目

题号	标题	题解	标签	难度	力扣
2100	适合野炊的日子		数组 动态规划 前缀和	🟠	🀄️ 🔗
2355	你能拿走的最大图书数量 🔒		栈 数组 动态规划 1+	🔴	🀄️ 🔗
2393	严格递增的子数组个数 🔒		数组 数学 动态规划	🟠	🀄️ 🔗