/** 53.Maximum Subarray * 2016-5-7 by Mingyang * 如果我們從頭遍歷這個數組。對于數組中的其中一個元素，它只有兩個選擇： 1.* 要么加入之前的數組加和之中（跟別人一組） * 2. 要么自己單立一個數組（自己單開一組）* 所以對于這個元素應該如何選擇，就看他能對哪個組的貢獻大。如果跟別人一組* 能讓總加和變大，還是跟別人一組好了；如果自己起個頭一組，自己的值比之前加和的值還要大，那么還是自己單開一組好了。* 所以利用一個dp數組，記錄每一輪sum的最大值，dp[i]表示當前這個元素是跟之前數組加和一組還是自己單立一組好，然后維護一個全局最大值即位答案* 那么這道題目開始想能不能用maxSubArray(int A[], int i, int j), which means the maxSubArray for A[i: j].* 但是這么寫子函數就很難找到這種關系。那么我們接下來就怎么做呢？* maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element.* 那么就下來的關系就是：* dp[i] = Math.max(A[i], dp[i - 1] + A[i]);* 也就是說對于A[i]到底加不加進來，我們只需要看這個加進來大還是單獨大。* 因為你如果加進來都比單獨大，那么后面還是一個增量。* 千萬不要寫成：dp[i] = Math.max(dp[i-1], dp[i - 1] + A[i]);
* Kadan's algorithm O(n) time and O(1) space
*/public static int maxSubArray(int[] A) {int[] dp = new int[A.length];int max = A[0];dp[0] = A[0];for (int i = 1; i < A.length; i++) {dp[i] = Math.max(A[i], dp[i - 1] + A[i]);
// 這里只比較了自己另外開一個，和原來的加一起開的區別max = Math.max(max, dp[i]);}
//不是每一個dp都是返回最后一個dp值哦！有可能返回全局變量return max;}/** 下面是我自己的解法，開始想的有點復雜，然后后面仔細列舉一下也是蠻簡單的，這里用了一個dp數組* dp[i]表示包括i在內的連續數組的最大值，而不是到i最優的結果* [-1,-2]那么dp[1]=-3,因為要把-2包括進來* 那么如果每個數自己就很大，比加起前面累積的dp還大，那么久自成一家* 否則的話需要加起來，每次更新dp的時候與全局變量max比較一下*/public int maxSubArray1(int[] nums) {int len=nums.length;int max=nums[0];int[] dp=new int[len];dp[0]=nums[0];for(int i=1;i<len;i++){if(nums[i]>nums[i]+dp[i-1]){dp[i]=nums[i];max=Math.max(max,dp[i]);}else{dp[i]=dp[i-1]+nums[i];max=Math.max(max,dp[i]);}}return max;}
?
