最大升序子数组和
难度:
标签:
题目描述
代码结果
运行时间: 18 ms, 内存: 16.2 MB
/*
思路:
1. 使用Java Stream对数组进行处理。
2. 用一个IntStream.range遍历数组索引,通过filter和mapToObj创建升序子数组的流。
3. 使用mapToInt和max获取最大的升序子数组和。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxAscendingSum(int[] nums) {
return IntStream.range(0, nums.length)
.mapToObj(i -> new int[]{i, nums[i]})
.filter(arr -> arr[0] == 0 || nums[arr[0]] <= nums[arr[0] - 1])
.mapToInt(arr -> IntStream.range(arr[0], nums.length)
.takeWhile(j -> j == arr[0] || nums[j] > nums[j - 1])
.map(j -> nums[j])
.sum())
.max()
.orElse(0);
}
}
解释
方法:
此题解采用遍历一次数组的方法,通过一个循环检查每个元素是否大于前一个元素,以此判断是否继续属于当前的升序子数组。如果当前元素大于前一个元素,则将其加到当前子数组的和中(current_sum);如果不是,则比较并更新最大子数组和(max_sum),并重新开始计算新的子数组的和。最后,循环结束后,再次更新最大子数组和,以确保最后一个升序子数组被考虑。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法结束时,对 current_sum 进行最后一次比较更新 max_sum 的原因是什么?
▷🦆
为什么在重新设置 current_sum 时选择当前的 nums[i] 而不是从0开始?
▷🦆
如果数组中所有元素相等会发生什么情况?算法是否能正确处理这种特殊情况?
▷🦆
在算法实现中,有没有考虑到 nums 为空数组的情况?如何处理这种边界情况?
▷