巨硬面试题：最大子数组
資深大佬 : zzzrf 1
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
样例 1:
输入：[−2,2,−3,4,−1,2,1,−5,3] 输出：6 解释：符合要求的子数组为[4,−1,2,1]，其最大和为 6 。 样例 2:
输入：[1,2,3,4] 输出：10 解释：符合要求的子数组为[1,2,3,4]，其最大和为 10 。 在线做题地址
算法
贪心
算法分析
- 题目要求给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。若直接暴力枚举子数组，时间复杂度需要 O(N2)；
- 由于题目要求是子数组最大和，因此可以利用贪心思想，通过局部的子数组最大，进而得到整体的最优解；
- 需要注意贪心的策略不能有后效性；
算法步骤
- 定义 maxAns 记录全局最大值，即结果； sum 记录当前子数组的和；
- 初始化：maxAns=Integer.MIN_VALUE; sum=0; 因为数组可以全为负数，因此 maxAns 不能直接初始化为 0 ；
- 遍历整数数组：
- Sum 累加当前的值；
- 若当前 sum>maxAns，更新 maxAns=sum ；
- 若当前 sum<0，表示当前的子数组和已经为负，累加到后面会使和更小，因此令 sum=0，相当于放弃当前的子数组，重新开始；
复杂度
- 时间复杂度：O(N),N 为数组长度
- 只需要遍历一遍数组就能找到答案；
- 空间复杂度：O(1)
- 只需要用到 maxAns 和 sum 两个变量.
public class Solution { /** * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ public int maxSubArray(int[] nums) { // maxAns 记录全局最大值 sum 记录当前子数组的和 int maxAns = Integer.MIN_VALUE, sum = 0; // 贪心 for (int i = 0; i < nums.length; i++) { sum += nums[i]; maxAns = Math.max(maxAns, sum); sum = Math.max(sum, 0); } return maxAns; } } 大佬有話說 (19)