題目描述（簡單難度）

給一個數(shù)組，找出一個連續(xù)的子數(shù)組，長度任意，和最大。

解法一 動態(tài)規(guī)劃思路一

用一個二維數(shù)組 dp[ i ] [ len ] 表示從下標(biāo) i 開始，長度為 len 的子數(shù)組的元素和。

這樣長度是 len + 1 的子數(shù)組就可以通過長度是 len 的子數(shù)組去求，也就是下邊的遞推式，

dp [ i ] [ len + 1 ] = dp[ i ] [ len ] + nums [ i + len - 1 ]。

當(dāng)然，和第 5 題一樣，考慮到求 i + 1 的情況的時候，我們只需要 i 時候的情況，所有我們其實沒必要用一個二維數(shù)組，直接用一維數(shù)組就可以了。

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int max = Integer.MIN_VALUE;
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            //直接覆蓋掉前邊對應(yīng)的情況就行
            dp[i] = dp[i] + nums[i + len - 1];
            //更新 max
            if (dp[i] > max) {
                max = dp[i];
            }
        }
    }
    return max;
}

時間復(fù)雜度：O（n2）。

空間復(fù)雜度：O（n）。

解法二 動態(tài)規(guī)劃思路二

參考這里。

用一個一維數(shù)組 dp [ i ] 表示以下標(biāo) i 結(jié)尾的子數(shù)組的元素的最大的和，也就是這個子數(shù)組最后一個元素是下邊為 i 的元素，并且這個子數(shù)組是所有以 i 結(jié)尾的子數(shù)組中，和最大的。

這樣的話就有兩種情況，

• 如果 dp [ i - 1 ] < 0，那么 dp [ i ] = nums [ i ]。
• 如果 dp [ i - 1 ] >= 0，那么 dp [ i ] = dp [ i - 1 ] + nums [ i ]。

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int max = nums[0];
    dp[0] = nums[0];
    for (int i = 1; i < n; i++) {
        //兩種情況更新 dp[i]
        if (dp[i - 1] < 0) {
            dp[i] = nums[i];
        } else {
            dp[i] = dp[i - 1] + nums[i];
        }
        //更新 max
        max = Math.max(max, dp[i]);
    }
    return max;
}

時間復(fù)雜度： O（n）。

空間復(fù)雜度：O（n）。

當(dāng)然，和以前一樣，我們注意到更新 i 的情況的時候只用到 i - 1 的時候，所以我們不需要數(shù)組，只需要兩個變量。

public int maxSubArray(int[] nums) {
    int n = nums.length;
    //兩個變量即可
    int[] dp = new int[2];
    int max = nums[0];
    dp[0] = nums[0];
    for (int i = 1; i < n; i++) {
        //利用求余，輪換兩個變量
        if (dp[(i - 1) % 2] < 0) {
            dp[i % 2] = nums[i];
        } else {
            dp[i % 2] = dp[(i - 1) % 2] + nums[i];
        }
        max = Math.max(max, dp[i % 2]);
    }
    return max;
}

時間復(fù)雜度： O（n）。

空間復(fù)雜度：O（1）。

再粗暴點，直接用一個變量就可以了。

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int dp = nums[0];
    int max = nums[0]; 
    for (int i = 1; i < n; i++) {
        if (dp < 0) {
            dp = nums[i];
        } else {
            dp= dp + nums[i];
        }
        max = Math.max(max, dp);
    }
    return max;
}

而對于

if (dp < 0) {
    dp = nums[i];
} else {
    dp= dp + nums[i];
}

其實也可以這樣理解，

dp= Math.max(dp + nums[i],nums[i]);

然后就變成了這里提到的算法。

解法三 折半

題目最后說

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

[這里](If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.)找到了種解法，分享下。

假設(shè)我們有了一個函數(shù) int getSubMax(int start, int end, int[] nums) ，可以得到 num [ start, end ) （左包右不包) 中子數(shù)組最大值。

如果， start == end，那么 getSubMax 直接返回 nums [ start ] 就可以了。

if (start == end) {
    return nums[start];
}

然后對問題進(jìn)行分解。

先找一個 mid ， mid = ( start + end ) / 2。

然后，對于我們要找的和最大的子數(shù)組有兩種情況。

• mid 不在我們要找的子數(shù)組中

  這樣的話，子數(shù)組的最大值要么是 mid 左半部分?jǐn)?shù)組的子數(shù)組產(chǎn)生，要么是右邊的產(chǎn)生，最大值的可以利用 getSubMax 求出來。

  int leftMax = getSubMax(start, mid, nums);
  int rightMax = getSubMax(mid + 1, end, nums);
  

• mid 在我們要找的子數(shù)組中

  這樣的話，我們可以分別從 mid 左邊擴展，和右邊擴展，找出兩邊和最大的時候，然后加起來就可以了。當(dāng)然如果，左邊或者右邊最大的都小于 0 ，我們就不加了。

  int containsMidMax = getContainMidMax(start, end, mid, nums);
  private int getContainMidMax(int start, int end, int mid, int[] nums) {
      int containsMidLeftMax = 0; //初始化為 0 ，防止最大的值也小于 0 
      //找左邊最大
      if (mid > 0) {
          int sum = 0;
          for (int i = mid - 1; i >= 0; i--) {
              sum += nums[i];
              if (sum > containsMidLeftMax) {
                  containsMidLeftMax = sum;
              }
          }
  
      }
      int containsMidRightMax = 0;
      //找右邊最大
      if (mid < end) {
          int sum = 0;
          for (int i = mid + 1; i <= end; i++) {
              sum += nums[i];
              if (sum > containsMidRightMax) {
                  containsMidRightMax = sum;
              }
          }
      }
      return containsMidLeftMax + nums[mid] + containsMidRightMax;
  }
  

  最后，我們只需要返回這三個中最大的值就可以了。

綜上，遞歸出口，問題分解就都有了。

public int maxSubArray(int[] nums) {
    return getSubMax(0, nums.length - 1, nums);
}

private int getSubMax(int start, int end, int[] nums) {
    //遞歸出口
    if (start == end) {
        return nums[start];
    }
    int mid = (start + end) / 2;
    //要找的數(shù)組不包含 mid，然后得到左邊和右邊最大的值
    int leftMax = getSubMax(start, mid, nums);
    int rightMax = getSubMax(mid + 1, end, nums);
    //要找的數(shù)組包含 mid
    int containsMidMax = getContainMidMax(start, end, mid, nums);
    //返回它們 3 個中最大的
    return Math.max(containsMidMax, Math.max(leftMax, rightMax));
}

private int getContainMidMax(int start, int end, int mid, int[] nums) {
    int containsMidLeftMax = 0; //初始化為 0 ，防止最大的值也小于 0 
    //找左邊最大
    if (mid > 0) {
        int sum = 0;
        for (int i = mid - 1; i >= 0; i--) {
            sum += nums[i];
            if (sum > containsMidLeftMax) {
                containsMidLeftMax = sum;
            }
        }

    }
    int containsMidRightMax = 0;
    //找右邊最大
    if (mid < end) {
        int sum = 0;
        for (int i = mid + 1; i <= end; i++) {
            sum += nums[i];
            if (sum > containsMidRightMax) {
                containsMidRightMax = sum;
            }
        }
    }
    return containsMidLeftMax + nums[mid] + containsMidRightMax;
}

時間復(fù)雜度：O（n log ( n )）。由于 getContainMidMax 這個函數(shù)耗費了 O（n）。所以時間復(fù)雜度反而相比之前的算法變大了。

空間復(fù)雜度：

總

解法一和解法二的動態(tài)規(guī)劃，只是在定義的時候一個表示以 i 開頭的子數(shù)組，一個表示以 i 結(jié)尾的子數(shù)組，卻造成了時間復(fù)雜度的差異。問題就是解法一中求出了太多的沒必要的和，不如解法二直接，只保存最大的和。解法三，一半一半的求，從而使問題分解，也是經(jīng)常遇到的思想。

更多詳細(xì)通俗題解詳見 leetcode.wang 。