leetcode
leetcode 1601 ~ 1650
最大升序子数组和

最大升序子数组和

难度:

标签:

题目描述

代码结果

运行时间: 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 只有在遇到不满足升序条件的元素时才会与 max_sum 进行比较和可能的更新。如果数组的最后一个子数组是升序的,那么在循环结束时,这个升序子数组的和还没有与 max_sum 进行比较更新。因此,需要在循环结束后再进行一次比较,以确保包含数组末尾部分的升序子数组也被考虑进最大和中。
🦆
为什么在重新设置 current_sum 时选择当前的 nums[i] 而不是从0开始?
在算法中,当遇到一个元素不满足升序条件时,意味着前一个升序子数组已经结束,需要开始一个新的子数组。新子数组的起始元素就是当前的 nums[i],因此 current_sum 需要重置为 nums[i]。如果从0开始,将无法正确计算新子数组的和,因为这会忽略掉当前这个元素的值。
🦆
如果数组中所有元素相等会发生什么情况?算法是否能正确处理这种特殊情况?
如果数组中所有元素相等,那么每个元素都不会大于其前一个元素,因此算法中的 current_sum 将在每个元素处被重置为当前元素的值。最终,max_sum 将为单个元素的值,即元素的最大值。算法可以正确处理这种情况,虽然所有元素相同,但输出将是单个元素的值,这在逻辑上是一致的。
🦆
在算法实现中,有没有考虑到 nums 为空数组的情况?如何处理这种边界情况?
在当前的实现中,没有直接检查 nums 是否为空。如果 nums 为空,将在尝试访问 nums[0] 时抛出 IndexError 异常。为了优雅地处理这种情况,应该在函数开始时加入一个检查:如果 nums 为空,则直接返回 0。这样可以避免异常并正确处理空数组的情况。

相关问题