題目描述
求一個數(shù)組的子數(shù)組最大和
例如[3,-2,1,6,-9,1,2,3]
那么這個數(shù)組的子數(shù)組最大和為8[3,-2,1,6]
[leetcode53]https://leetcode.com/problems/maximum-subarray/
思路：
- 首先當(dāng)然可以暴力的使用兩層循環(huán)找到這個最大的子數(shù)組，但是太費時間了们妥。
- 動態(tài)規(guī)劃來求解
算法流程
- 使用兩個變量cur和res,cur代表求解過程中的一個臨時變量，代表累加到當(dāng)前位置的一個片段最大勉吻，res代表全局的最大监婶，實時更新。
- 遍歷數(shù)組齿桃，cur為數(shù)組元素的累加和惑惶，如果cur<0，先把cur置為0短纵，然后cur加上當(dāng)前位置元素带污，并比較cur和res的大小，更新res香到。遍歷結(jié)束后返回res即可鱼冀。
算法原理
思考位置i,如果在位置i cur大于0，證明你從i位置開始的最大和肯定沒有從i之前開始的大,假如你cur<0了悠就，那么從i 開始肯定比從i之前開始大千绪，因為你前綴為負(fù)數(shù)，為何不直接丟棄前綴呢梗脾。所以有了我們算法的更新策略荸型。
代碼
public class Solution {
public int maxSubArray(int[] nums) {
if(nums==null||nums.length==0)
return 0;
int cur=nums[0];
int res=nums[0];
for(int i=1;i<nums.length;i++){
cur=cur<0?0:cur;
cur+=nums[i];
res=Math.max(cur,res);
}
return res;
}
}
