连续数列
难度:
标签:
题目描述
You are given an array of integers (both positive and negative). Find the contiguous sequence with the largest sum. Return the sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum 6.
Follow Up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
代码结果
运行时间: 27 ms, 内存: 16.8 MB
/*
* 题目思路：
* 1. 使用 Java Stream API 可以简化代码，但要注意我们仍需手动维护两个变量来存储当前最大和与全局最大和。
* 2. 使用 IntStream 对数组进行流处理，在流中更新 currentMax 和 globalMax。
* 3. 使用 reduce 方法来进行聚合计算。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxSubArray(int[] nums) {
// 初始化 currentMax 和 globalMax
int[] result = IntStream.of(nums).reduce(new int[]{nums[0], nums[0]}, (acc, num) -> {
int currentMax = Math.max(num, acc[0] + num); // 更新当前子数组最大和
int globalMax = Math.max(acc[1], currentMax); // 更新全局最大和
return new int[]{currentMax, globalMax};
});
return result[1]; // 返回全局最大和
}
}解释
方法:
题解采用了Kadane算法解决问题。算法的核心思想是通过遍历数组，维护一个当前连续子数组的最大和(prefix)以及全局的最大和(ans)。对于数组中的每个元素，算法检查当前连续子数组的和(prefix)是否为负数：如果是负数，表示加上当前元素后不可能使得子数组和增大，因此重新开始计算新的子数组和，即将prefix重置为当前元素的值；如果不是负数，将当前元素加到prefix上。同时，使用ans记录下遍历过程中遇到的最大的prefix值。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在Kadane算法中，如果当前子数组和(prefix)为负数就重新设置prefix为当前元素值？这种做法有什么理论依据？
▷🦆
在Kadane算法中，如果数组中所有元素都是负数怎么处理？算法是否仍能有效地找到最大的子数组和？
▷🦆
Kadane算法中提到的全局最大子数组和(ans)，在每次迭代过程中如何更新？是否每次迭代都需要比较ans和prefix？
▷