1、地址

https://leetcode-cn.com/problems/maximum-subarray/

2、题面分析

题目

image.png

题目信息

  • 输入是一个整数数组，返回是一个整数
  • 返回的整数：一个连续子数组和
  • 如果输入的数组不为空，则返回的整数不为空

3、暴力求解 - - O(N2)

求解思路

  • 使用暴力枚举对所有可能的头部指针i和尾部指针j，求sum(nums[i,j])，记录其中最大的值放入maxSum变量中

    代码实现1 - - 超出时间限制

    1. class Solution {
    2.   public int maxSubArray(int[] nums) {
    3.       int len = nums.length;
    4.       if(len == 1){
    5.           return nums[0];
    6.       }
    7.       int maxSum = Integer.MIN_VALUE;
    8.       int sum;
    9.       for(int i = 0; i < len; i++){
    10.           sum = nums[i];
    11.           if(maxSum < sum){
    12.               maxSum = sum;
    13.           }
    14.           for(int j = i + 1; j < len; j++){
    15.               sum += nums[j];
    16.               if(maxSum < sum){
    17.                   maxSum = sum;
    18.               }
    19.           }
    20.       }
    21.       return maxSum;
    22.   }
    23. }

    TIPS: 执行的时候会超出leetcode的时间限制

    代码实现2 - - 压缩数组

    虽然压缩了数组但是还是慢

    1. class Solution {
    2.   public int maxSubArray(int[] nums) {
    3.       int len = nums.length;
    4.       if(len == 1){
    5.           return nums[0];
    6.       }
    7.       int startIndex = 0;
    8.       int tempSum = nums[0];
    9.       // 应对全负数
    10.       int max = tempSum;
    11.       for(int i = 1; i < len; i++){
    12.           if(nums[i] > max){
    13.               max = nums[i];
    14.           }
    15.           if((tempSum <= 0 && nums[i] <= 0) || (tempSum >= 0 && nums[i] >= 0 ) ){
    16.               tempSum += nums[i];
    17.           }else{
    18.               nums[startIndex++] = tempSum;
    19.               tempSum = nums[i];
    20.           }
    21.       }
    22.       nums[startIndex++] = tempSum;
    23.       len = startIndex;
    25.       int maxSum = Integer.MIN_VALUE;
    26.       int sum;
    27.       for(int i = 0; i < len; i++){
    28.           sum = nums[i];
    29.           if(maxSum < sum){
    30.               maxSum = sum;
    31.           }
    32.           for(int j = i + 1; j < len; j++){
    33.               sum += nums[j];
    34.               if(maxSum < sum){
    35.                   maxSum = sum;
    36.               }
    37.           }
    38.       }
    39.       return maxSum > max ? maxSum : max;
    40.   }
    41. }

    4、贪心算法

    求解思路

  • 从下标0开始累加并更新maxSum，当加到某个数使得当前和<0，从下一个数开始重新计算加和.

    代码实现

    1. class Solution {
    2.   public int maxSubArray(int[] nums) {
    3.       int len = nums.length;
    4.       if(len == 1){
    5.           return nums[0];
    6.       }
    7.       int maxSum = Integer.MIN_VALUE;
    8.       int sum = 0;
    9.       for(int i = 0; i < len; i++){
    10.           sum += nums[i];
    11.           if(sum > maxSum){
    12.               maxSum = sum;
    13.           }
    14.           if(sum < 0){
    15.               sum = 0;
    16.           }
    17.       }
    18.       return maxSum;
    19.   }
    20. }

    5、动态规划算法

    求解思路

    共同点

  • 基于子问题求解（无后效性）

  • 策略驱动

不同点：

  • 贪心：
    • 局部最优可以得到全局最优
    • 解具备一定的单调性
  • 动态规划：
    • 每个子问题可能会记录多种状态，不一定只存储最优
    • 对解的单调性要求不高

动态规划方程：
DP(k) = f(DP(k-1), element(k))

DP(k)：表示nums[0,k]

代码实现

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int len = nums.length;
  4.         if(len == 1){
  5.             return nums[0];
  6.         }
  7.         int[] dp = new int[len];
  8.         dp[0] = nums[0];
  9.         int maxSum = dp[0];
  10.         for(int i = 1; i < len; i++){
  11.             dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
  12.             if(dp[i] > maxSum){
  13.                 maxSum = dp[i];
  14.             }
  15.         }
  16.         return maxSum;
  17.     }
  18. }

6、分治法

  • 问题递归分割：分治法会将原问题分成N个子问题分别进行求解。如果子问题的规模依旧非常大（不能直观的得到答案的规模），那么需要对子问题递归的进行分割
  • 临界问题求解：可以“简单”求解的问题。一般对临界问题的求解消耗的时间都是O(1)
  • 子问题解的合并：当已知子问题的解时，通过这些解得到父问题的答案

算法核心：将大化小，对小问题进行求解，从而求解出原问题
算法难点：如何分割，以及如何将解合并
分治法的重要思想：假设当前已经拥有子问题的解

求解思路

  • 子问题的解与父问题的解
    • 父问题S的解在左实例S1中：递归求解S1
    • 父问题S的解在右实例S2中：递归求解S2
    • 父问题S的解被分在左右两个实例中：
      • 在S1中，求解是以i作为解的右下标解区间
      • 在S2中，求解时以i+1作为解的左下标的解区间

代码实现

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int len = nums.length;
  4.         if(len == 1){
  5.             return nums[0];
  6.         }
  7.         return maxSumSubArray(nums, 0, len - 1);
  8.     }
  10.     public int maxSumSubArray(int[] nums, int leftIndex, int rightIndex){
  11.         int arrayLen = rightIndex - leftIndex + 1;
  12.         if(arrayLen == 1){
  13.             return nums[leftIndex];
  14.         }
  15.         int midIndex = (rightIndex - leftIndex) / 2 + leftIndex;
  16.         int rightMaxSub = maxSumSubArray(nums, midIndex + 1, rightIndex);
  17.         int leftMaxSub = maxSumSubArray(nums, leftIndex, midIndex);
  18.         int midMaxSub = maxSumContainsMidIndex(nums, midIndex,leftIndex, rightIndex);
  19.         return Math.max(midMaxSub, Math.max(leftMaxSub, rightMaxSub));
  20.     }
  22.     public int maxSumContainsMidIndex(int[] nums, int midIndex, int leftIndex, int rightIndex){
  23.         int leftMax = Integer.MIN_VALUE;
  24.         int rightMax = leftMax;
  25.         int sum = 0;
  26.         if(leftIndex < midIndex){
  27.             for(int i = midIndex; i >= leftIndex; i-- ){
  28.                 sum += nums[i];
  29.                 if(sum > leftMax){
  30.                     leftMax = sum;
  31.                 }
  33.             }
  34.         }else{
  35.             leftMax = nums[midIndex];
  36.         }
  38.         if(rightIndex > midIndex){
  39.             sum = 0;
  40.             for(int i = midIndex + 1; i <= rightIndex; i++ ){
  41.                 sum += nums[i];
  42.                 if(sum > rightMax){
  43.                     rightMax = sum;
  44.                 }
  46.             }
  47.         }else{
  48.             rightMax = 0;
  49.         }
  50.         return leftMax + rightMax;
  51.     }
  52. }