動态規劃-連續子數組的最大和-JZ30

描述

輸入一個整型數組，數組裡有正數也有負數。數組中的一個或連續多個整數組成一個子數組。求所有子數組的和的最大值。要求時間複雜度為 O(n).

示例1

輸入： [1,-2,3,10,-4,7,2,-5]

傳回值： 18

說明：輸入的數組為{1,-2,3,10,—4,7,2,一5}，和最大的子數組為{3,10,一4,7,2}，是以輸出為該子數組的和 18。

思路

直接用簡化動态規劃，使用一個變量sum來表示目前連續的子數組和，以及一個變量res來表示中間出現的最大的和。

時間複雜度O(n)，空間複雜度O(1)

代碼

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        //res表示所有子數組的和的最大值
        int res = array[0];
        //sum表示包含目前連續的子數組和
        int sum = array[0];
        for (int i = 1; i < array.length; ++i) {
            sum = max(sum + array[i], array[i]);
            res = max(res, sum);
        }
        return res;
    }
    private int max(int i, int j) {
        return i > j ? i : j;
    }
}