給定一個(gè)整數(shù)數(shù)組 nums 徐紧，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）挟鸠，返回其最大和意乓。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大拆檬，為 6。
進(jìn)階:
如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法屡贺，嘗試使用更為精妙的分治法求解蠢棱。
方法一：暴力法
執(zhí)行用時(shí) : 133 ms, 在Maximum Subarray的Java提交中擊敗了5.02% 的用戶(hù)
內(nèi)存消耗 : 40.7 MB, 在Maximum Subarray的Java提交中擊敗了64.93% 的用戶(hù)
class Solution {
public int maxSubArray(int[] nums) {
int sumMax = Integer.MIN_VALUE;
for(int i=0; i<nums.length;i++){
int sum = 0;
for(int j=i; j<nums.length;j++){
sum += nums[j];
sumMax = Math.max(sum, sumMax);
}
}
return sumMax;
}
}
方法二：動(dòng)態(tài)規(guī)劃
執(zhí)行用時(shí) : 2 ms, 在Maximum Subarray的Java提交中擊敗了98.86% 的用戶(hù)
內(nèi)存消耗 : 38 MB, 在Maximum Subarray的Java提交中擊敗了88.05% 的用戶(hù)
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int sum = 0;
for (int num : nums) {
if(sum>0){
sum += num;
}else{
sum = num;
}
maxSum = Math.max(sum, maxSum);
}
return maxSum;
}
}
