一嘿棘、問題描述
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
二、解決思路
思路一：暴力法慧库，通過兩下標(biāo)求出每個(gè)子數(shù)組和并取最大分唾，O(n^3)
思路二：動(dòng)態(tài)規(guī)劃法溅呢，分析思路一可以發(fā)現(xiàn)骡湖，暴力法存在很多重復(fù)計(jì)算幢竹，在終點(diǎn)下標(biāo)加一的時(shí)候，如果當(dāng)前值小于0時(shí)伊佃，直接可以舍棄該結(jié)果窜司，因此，需要找到動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程航揉，通過舉例可以找到如下規(guī)律：
dp[i] = max(arr[i], dp[i - 1] + arr[i])塞祈，其中arr為元素?cái)?shù)組，dp[i]為當(dāng)前數(shù)組元素的最大子數(shù)組和帅涂，時(shí)空O(n)
思路三：對思路二的空間復(fù)雜度進(jìn)行優(yōu)化议薪，題目只要求求出最大子數(shù)組和，可以通過兩局部變量來替代數(shù)組媳友，O(n)
三斯议、算法實(shí)現(xiàn)
思路二
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int lens = nums.length;
int[] dp = new int[lens];
dp[0] = nums[0];
int max = dp[0];
for(int i = 1; i < lens; i++){
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
max = Math.max(max, dp[i]);
}
return max;
}
思路三
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int lens = nums.length;
int max = nums[0];
int local = nums[0];
for(int i = 1; i < lens; i++){
local = Math.max(local + nums[i], nums[i]);
max = Math.max(local, max);
}
return max;
}
