一、题目
给你一个正整数组成的数组 nums
,返回 nums
中一个 升序 子数组的最大可能元素和。子数组是数组中的一个连续数字序列。已知子数组 [numsl, numsl 1, ..., numsr-1, numsr]
,若对所有 i(l <= i < r)
,numsi < numsi 1
都成立,则称这一子数组为 升序 子数组。注意,大小为 1
的子数组也视作 升序 子数组。
二、示例
2.1> 示例 1:
【输入】nums = [10,20,30,5,10,50] 【输出】65 【解释】[5,10,50] 是元素和最大的升序子数组,最大元素和为 65 。
2.2> 示例 2:
【输入】nums = [10,20,30,40,50] 【输出】150 【解释】[10,20,30,40,50] 是元素和最大的升序子数组,最大元素和为 150 。
2.3> 示例 3:
【输入】nums = [12,17,15,13,10,11,12] 【输出】33 【解释】[10,11,12] 是元素和最大的升序子数组,最大元素和为 33 。
2.4> 示例 4:
【输入】nums = [100,10,1] 【输出】100
提示:
- •
1
<= nums.length <=100
- •
1
<= nums[i] <=100
三、解题思路
根据题目描述,我们需要找到nums数组中的升序子数组中最大的元素和。那我们其实只需要在遍历数组元素的过程中,对于nums[i - 1] < nums[i]
的情况执行加和计算(total)即可。那么,如果我们发现nums[i - 1] >= nums[i]
情况出现的时候,就说明已经不是升序数组了,那么此时我们需要将total值重置为0,并且由于nums[i]就是下一个升序子数组的第一个元素,所以执行total = nums[i]
即可。
由于题目中要求返回最大的元素和,所以,在每次遍历元素的时候,我们将result和total中的最大值赋值给result,当整个数组nums中的元素都遍历完毕之后,result值就是数组中的升序子数组中最大的元素和。具体操作如下图所示:
四、代码实现
代码语言:javascript复制class Solution {
public int maxAscendingSum(int[] nums) {
int result = nums[0], total = result;
for (int i = 1; i < nums.length; i ) {
if (nums[i - 1] < nums[i]) total = nums[i];
else total = nums[i];
result = Math.max(result, total);
}
return result;
}
}