給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素）银酗，返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大徒像，為 6黍特。
首先我們來分析題意：我們設(shè)定f(n)為數(shù)組長度為n的最大子序和
我們分析
當(dāng)n=1時 需要比較的數(shù)組組合為 [1]
當(dāng)n=2時 需要比較的數(shù)組組合為 [1][2][1,2]
當(dāng)n=3時 需要比較的數(shù)組組合為 [1][2][1,2][3][3,2][3,2,1]
當(dāng)n=4時 需要比較的數(shù)組組合為 [1][2][1,2][3][3,2][3,2,1][4][4,3][4,3,2][4,3,2,1]
當(dāng)n=5時 需要比較的數(shù)組組合為 [1][2][1,2][3][3,2][3,2,1][4][4,3][4,3,2][4,3,2,1][5][5,4][5,4,3][5,4,3,2][5,4,3,2,1]
分析比較n值變換時候消除不同n值之間重復(fù)的組合
最終可以得到變形后需要比較的數(shù)組隊列
當(dāng)n=1時 需要比較的數(shù)組組合為 [1]
當(dāng)n=2時 需要比較的數(shù)組組合為 [2] [1,2]
當(dāng)n=3時 需要比較的數(shù)組組合為 [3] [3,2] [3,2,1]
當(dāng)n=4時 需要比較的數(shù)組組合為 [4] [4,3] [4,3,2] [4,3,2,1]
當(dāng)n=5時 需要比較的數(shù)組組合為 [5][5,4][5,4,3][5,4,3,2][5,4,3,2,1]
設(shè)定第n層所有需要比較的子序數(shù)組為 f(n)
比較相鄰兩層之間的數(shù)據(jù)可以知道 f(n)中的數(shù)組相當(dāng)于 [n]和f(n-1)的數(shù)組循環(huán)加[n]元素
設(shè)定dp[n]為第n層中需要比較的最大子序和
dp[n] = max([n],[n]+dp[n-1])
public int maxSubArray(int[] nums) {
int position = nums[0];
int result = position;
for(int i=1;i<nums.length;i++) {
position = Math.max(nums[i], position+nums[i]);
result = Math.max(result,position);
}
return result;
}
