【算法笔记：求最大子数组和】暴力求解、动态规划、贪心法
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入输出
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
解法一：暴力求解-O(n2)
将每一个元素作为开始元素，遍历求和，比较获取每一轮的最大值；时间复杂度都是O(n2) 代码如下:
// 暴力解法:将每一个元素作为开始元素，遍历求和，比较获取每一轮的最大值/*** @param {number[]} nums* @return {number}*/var maxSubArray = function(nums) {// 初始化最大值let max=nums[0];// 第一次遍历数组for(let i=0;i<nums.length;i++){// 每次遍历 sum都初始为0let sum=0;// 遍历数组求和for(let j=i;j<nums.length;j++){sum+=nums[j];if(sum>max){max=sum;}}}return max;};let res=maxSubArray([-2,1,-3,4,-1,2,1,-5,4]);
解法二：动态规划-O(n)
若前一个元素大于0，则将其加到当前元素上。否则，保持当前元素值不变。原理:若之前的元素小于0，则对当前元素并无增益；如果大于0，则对当前元素有增益，加到当前元素上。
// 动态规划:若前一个元素大于0，则将其加到当前元素上/*** @param {number[]} nums* @return {number}*/var maxSubArray = function(nums) {// 数组长度let length=nums.lengthfor(let i=1;i<length;i++){if(nums[i-1]>0){nums[i]+=nums[i-1];}}// 排序nums=nums.sort((a,b)=>{return b-a})return nums[0]};let res=maxSubArray([-2,1,-3,4,-1,2,1,-5,4]);
解法三：贪心法-O(n)
遍历数组，并计算序列和，若当前选择元素之前的序列和小于0，则丢弃当前元素之前的数列。
当之前序列和小于0的序列与当前元素组成新的序列，那么新的序列和（currentSum）只会小于当前元素的值，那么这次相加就无意义了。因此要丢弃之前的序列和，将当前所选元素定义为新的序列和的第一个元素；
原理跟动态规划思路大同小异；无非是之前值或者序列和对后续求和有无增益
// 贪心法:若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列///*** @param {number[]} nums* @return {number}*/var maxSubArray = function(nums) {//当前连续和let currentSum;//之前连续let preSum=0 ;//最大连续和let maxSum=nums[0];for (let i=-0;i<nums.length; i++) {num=nums[i]if (preSum <= 0) {//若之前和小于0，则丢弃之前和，并将当前所指元素赋予currentSumcurrentSum = num;} else {//若之前和大于0，则将之前和与当前相加currentSum = preSum + num;}if (currentSum > maxSum) {maxSum = currentSum;}preSum = currentSum;}return maxSum};let res=maxSubArray([-2,1,-3,4,-1,2,1,-5,4]);
▼
编辑：杨玉凤