本系列導航：劍指offer（第二版）java實現(xiàn)導航帖](http://www.itdecent.cn/p/010410a4d419)

面試題42：連續(xù)子數(shù)組的最大和

題目要求：
輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負數(shù)。數(shù)組中一個或連續(xù)多個整數(shù)組成一個子數(shù)組。求所有子數(shù)組的和的最大值，要求時間復雜度為o(n)。

解題思路：
暴力求解，簡單直接，但時間復雜度o(n^2)。
其實這種最值問題，很容易讓人想到動態(tài)規(guī)劃。對于數(shù)據(jù)data[],申請一個數(shù)組dp[]，定義dp[i]表示以data[i]為末尾元素的子數(shù)組和的最大值。dp的初始化及遞推公式可表示為

dp[i] =  data[i]            i=0或dp[i-1]<=0
         dp[i-1]+data[i]    i!=0且dp[i-1]>0

由于dp[i]僅與dp的前一個狀態(tài)有關，即在計算dp[i]時，dp[i-2],dp[i-3]......,dp[0]對于dp[i]沒有影響，因此可以省去dp數(shù)組，用一個變量記錄當前dp值，用另一個變量maxdp記錄出現(xiàn)的最大的dp值。如此處理后，時間復雜度為o(n)，空間復雜度為o(1)。

package chapter5;

/**
 * Created with IntelliJ IDEA.
 * Author: ryder
 * Date  : 2017/8/1
 * Time  : 20:58
 * Description:連續(xù)子數(shù)組的最大和
 **/
public class P218_GreatestSumOfSubarrays {
    //動態(tài)規(guī)劃，遞歸公式：dp[i] =  data[i]          i=0或dp[i-1]<=0
    //                           dp[i-1]+data[i]  i!=0且dp[i-1]>0
    //由于只需知道前一個情況的dp值，因此可省去dp數(shù)組，申請個變量記錄即可
    public static int findGreatestSumOfSumArrays(int[] data){
        if(data==null || data.length==0)
            return 0;
        //dp[i]用于計算以data[i]為結尾元素的連續(xù)數(shù)組的最大和
        //maxdp用于記錄在上述過程中的最大的dp值
        int dp = data[0],maxdp = dp;
        for(int i=1;i<data.length;i++){
            if(dp>0)
                dp += data[i];
            else
                dp = data[i];
            if(dp>maxdp)
                maxdp = dp;
        }
        return maxdp;
    }
    public static void main(String[] args){
        int[] data = {1,-2,3,10,-4,7,2,-5};
        System.out.println(findGreatestSumOfSumArrays(data));
    }
}

運行結果

18