题目描述:
leetcode 题目链接： 53. 最大子数组和 - 力扣（LeetCode） (leetcode-cn.com)
解题思路分析：
题干最终的输出是连续子数组的最大和；
1. 贪心算法： 从局部最优中找到全局最优，局部最优就是不以负数开头的子数组最大的和；贪心策略只要目前子数组的和为负数，就从下一个数开始遍历，更新子数组的起始位置。
2. 动态规划： 下一个状态值依赖上一个状态值（详见下面解法的步骤）
不同解法：
/**
* @param {number[]} nums
* @return {number}
*/
/**
* 动态规划 V1
* 动态规划的解题步骤：
* 1.确定DP下标的含义： dp[i]表示以下标i开头的，长度为len的子数组的和
长度为len的和可以根据长度为(len-1)的计算，即在长度为(len-1)的基础上加上nums[i+len-1]
* 2.确定递推公式： 递推公式 dp[i] = dp[i] + dp[i+len-1]
* 3.初始化，下标和dp[i]都为0
* 4.确定遍历方向，从前往后，使用两层遍历：外层遍历是不同的长度，内层遍历是以不同的i开头
* 5.举例推导结果
*/
// !! 超出时间限制，但是思路没有错，示例运算没有问题
var maxSubArray = function(nums) {
var n = nums.length;
var dp = new Array(n);
dp.fill(0); // 以0填充数组
var res = -Infinity;
for(var len = 1; len <= n;len++){
for(var i = 0; i <= n-len; i++){
dp[i]=dp[i]+nums[i+len-1];//不断更新以i开头的子数组的和
if(dp[i] > res){
res = dp[i]; //更新子数组和的最大值
}
}
}
return res;
}
/**
* @param {number[]} nums
* @return {number}
*/
/**
* 动态规划 V2
* 动态规划的解题步骤：
* 1.确定DP下标的含义： dp[i]表示当前下标i之前的最大连续子序列和的最大值
(即所有以i为结尾的数组最大的和)
* 2.确定递推公式： 递推公式 dp[i] = max (dp[i-1]+nums[i],nums[i]) res = max(res,dp[i])
* 3.初始化，下标和dp[i]都为0
* 4.确定遍历方向，从前往后
* 5.举例推导结果
*/
var maxSubArray = function(nums) {
// 题目中没说，可写可不写
if(nums.length == 0){
return '无法进行判断';
}
var dp = new Array(nums.length);
dp[0]=nums[0];
// var res = dp[0];
for(var i = 1; len = nums.length,i<len; i++){
dp[i]= Math.max(dp[i-1]+nums[i],nums[i]); //状态转移公式；不断更新子数组的起始位置
// 更新最大值
// res = Math.max(res,dp[i]);
}
return Math.max(...dp); // 运行速度比较慢
// return res;
};
// 另外一种写法
var maxSubArray = function(nums){
var dp = nums[0]; // 代表当前子数组的和
var res = nums[0];
for(var i = 1; len = nums.length, i<len; i++){
if(dp<0){
dp = nums[i]; //负数总是拉低总和，所以更新起始位置（隐含的一种必要情况是，最终的结果一定是正数开头，如果含有正数）
}else{
dp = dp + nums[i];
}
// 更新max
res = dp>res? dp:res;
}
return res;
}
// 贪心算法
// 解题思路：1.最优解是不是一定在局部最优解里找到；2.选择的贪心策略，举不出来反例
// 只要是子数组之和是负数，就从零开始，因为负数再相加会拉低总和
var maxSubArray = function(nums){
var sum = 0;
var maxSum = -Infinity;
for(var i = 0; i<nums.length; i++){
sum += nums[i]; // 如果sum为0，说明更新了子数组的起始位置
// 更新全局最优
if(sum > maxSum){
maxSum = sum;
}
// 贪心
if(sum < 0){
sum = 0;
}
}
return maxSum;
}
参考链接：
代码随想录 (programmercarl.com)
代码随想录 (programmercarl.com)（我心中的新晋大神，语言贴地气儿，解法简单易懂）
53. Maximum Subarray · leetcode （有些解法，没有采用，可以参考看看~）
