leetcode-53：Maximum Subarray

本文主要是介绍leetcode-53：Maximum Subarray，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

声明：
1、本文仅为学习笔记，不得商用
2、文中所引文献，已在参考资料中说明，但部分来源于网络，出处无可考究，如果文中引用了您的原创，请您私信我
3、如果内容有错误或者不准确的地方请大家指正

题目网址
题目大意
解题思路
- 枚举法
- 分治法
- 动态规划
  - 递推式
  - 初值
  - 复杂度
  - 空间优化
  - 代码
  - 优化后的代码

题目网址

https://leetcode.com/problems/maximum-subarray/

题目大意

给定一个数组，求最长子数组，放回最长子数组的和

解题思路

枚举法

把所有的组合枚举一遍，时间复杂度较高

分治法

把数组分成两个部分，最长子数组要么在左面，要么在右面，要么经过中心点的最大子数组，是将复杂度为 $O(n*logn)$

动态规划

递推式

dp[i]表示以a[i]结尾的最大子树组的和
dp[i]=max(dp[i-1] + a[i],a[i])
包含a[i-1]：dp[i-1]+a[i]
不包含a[i-1]：a[i]

初值

dp[0]=a[0]
答案为max(dp[0,1…n-1])，中最大的数

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

空间优化

dp[i]需要存储吗？用一个变量优化空间复杂度
endHere = max(endHere + a[i],a[i])
answer = max(endHere,answer)

代码

public class Solution {public int maxSubArray(int[] nums) {if(nums == null || nums.length==0){return 0;}int len = nums.length;int[] dp = new int[len];dp[0] = nums[0];int answer = nums[0];for(int i = 1; i < len ; i++ ){dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);answer = Math.max(answer,dp[i]);}return answer;}
}

优化后的代码

public class Solution {public int maxSubArray(int[] nums) {if(nums == null || nums.length==0){return 0;}int len = nums.length;int endHere = nums[0];int answer = nums[0];for(int i = 1; i < len ; i++ ){endHere = Math.max(endHere+nums[i],nums[i]);answer = Math.max(answer,endHere);}return answer;}
}