最大子数组和
难度:
标签:
题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
代码结果
运行时间: 52 ms, 内存: 15.3 MB
/**
* 题目思路：
* 使用Java Stream API实现Kadane算法。我们通过IntStream和reduce操作来计算最大子数组和。
* 初始值使用一个int数组来保存当前和和最大和，
* 每次更新时，比较当前元素和当前和加上当前元素的大小来确定当前和。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxSubArray(int[] nums) {
return IntStream.range(0, nums.length)
.mapToObj(i -> new int[]{nums[i], nums[i]})
.reduce(new int[]{nums[0], nums[0]}, (a, b) -> {
a[1] = Math.max(b[0], a[1] + b[0]);
a[0] = Math.max(a[0], a[1]);
return a;
})[0];
}
}解释
方法:
这个题解使用了动态规划的思想。通过遍历数组，对于每个元素，判断将其加入当前子数组是否会使当前子数组的和增大。如果当前子数组的和小于0，那么加上当前元素会使子数组的和变小，因此将当前子数组的和重置为当前元素。否则，将当前元素加入子数组。同时，更新最大子数组和。最终返回遍历过程中得到的最大子数组和。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在动态规划的解法中，当当前子数组的和小于0时，选择将子数组的和重置为当前元素，而不是继续累加？
▷🦆
在动态规划的解法中，最大子数组和`max_sum`初始化为负无穷大是出于什么考虑？是否有其他可能的初始化方式？
▷🦆
题解中提到的动态规划解法有没有考虑到所有的边界情况，例如数组中所有元素都是负数，或者数组只包含一个元素的情况？
▷🦆
动态规划的方法是否能够有效处理数组长度非常大（接近105）的情况，对于这种情况有没有性能上的考量？
▷相关问题
买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
数组的度
给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例 1：
输入：nums = [1,2,2,3,1] 输出：2 解释： 输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。 连续子数组里面拥有相同度的有如下所示： [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] 最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。
示例 2：
输入：nums = [1,2,2,3,1,4,2] 输出：6 解释： 数组的度是 3 ，因为元素 2 重复出现 3 次。 所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。
提示：
nums.length在1到50,000范围内。nums[i]是一个在0到49,999范围内的整数。
最长湍流子数组
给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：
- 若
i <= k < j：- 当
k为奇数时，A[k] > A[k+1]，且 - 当
k为偶数时，A[k] < A[k+1]；
- 当
- 或 若
i <= k < j：- 当
k为偶数时，A[k] > A[k+1]，且 - 当
k为奇数时，A[k] < A[k+1]。
- 当
示例 1：
输入：arr = [9,4,2,10,7,8,8,1,9] 输出：5 解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
示例 2：
输入：arr = [4,8,12,16] 输出：2
示例 3：
输入：arr = [100] 输出：1
提示：
1 <= arr.length <= 4 * 1040 <= arr[i] <= 109