LeetCode-53-最大子数组和-贪心算法

贪心算法理论基础：
局部最优推全局最优
贪心无套路~
没有什么规律~
重点：每个阶段的局部最优是什么？

题目描述：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

解题思路：贪心算法，详细思路在注释中有~

代码实现：

class Solution {/*** 解题思路：贪心算法：当 加上一个数发现比当前连续和(sum)要小的时候直接舍掉，就从下一个正数重新开始计算* 注意：连续和是负数的时候丢弃，而不是遇到负数就丢弃* 暴力法：时间复杂度 O(n^2)* 贪心算法：时间复杂度 O(n)*/public int maxSubArray(int[] nums) {int len = nums.length;int sum = 0;// 连续和int maxSubSum = Integer.MIN_VALUE;// 最大连续和for (int i = 0; i < len; i++) {sum += nums[i];if (sum > maxSubSum){maxSubSum = sum;}if (sum < 0){sum = 0;// 更新 sum=0}}return maxSubSum;}
}