【LeetCode每日一题】53. 最大子数组和

https://leetcode.cn/problems/maximum-subarray/description/

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

方式一：暴力解法（超时）

先算出数组的前缀和，然后通过2个for循环遍历出所有的连续子数组。

/*** @param {number[]} nums* @return {number}*/
var maxSubArray = function(nums) {let prefixArr = [];let sum = 0;for(let num of nums){sum += num;prefixArr.push(sum);}prefixArr.unshift(0);// let max = prefixArr[0];let max = -Infinityfor(let i = 0; i < prefixArr.length-1; i++){for(let j = i+1 ; j < prefixArr.length; j++){max = Math.max(max, prefixArr[j] - prefixArr[i]);}}return max;
}

方式二：

寻找一个具有最大和的连续子数组，算出以每个元素结尾的最大和，在这些最大值里求最大值。

对于元素A来说，以它结束的最大值 = Math.max(元素A，元素A+前一个元素的最大值）

遍历，求出以每个元素结尾的最大值放在一个数组。

求该数组的最大值。

/*** @param {number[]} nums* @return {number}*/
var maxSubArray = function(nums) {let max = 0let arr = []**for(**let num of nums){max = Math.max(max+num, num);arr.push(max)}return Math.max(...arr);
};

根据方式二，可以在遍历的时候将数据就进行比较。

/*** @param {number[]} nums* @return {number}*/
var maxSubArray = function(nums) {let res = nums[0];let max = 0for(let num of nums){max = Math.max(max+num, num);res = Math.max(res, max);}return res;
};