描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

Tag

array | divide-and-conquer | dynamic-programming

思路

代码

方法一：暴力求解O(n3)

  1. public int maxSubArray(int[] nums) {
  2.         int maxSum =0;
  3.         for (int i = 0; i < nums.length; i++) {
  4.             for (int j = i; j < nums.length; j++) {
  5.                 int tempSum=0;
  7.                 for (int k = i; k <= j; k++) {
  8.                     tempSum += nums[k];
  9.                 }
  10.                 if (tempSum > maxSum) {
  11.                     maxSum=tempSum;
  12.                 }
  13.             }
  14.         }
  15.         return maxSum;
  16.     }

方法二：暴力求解改进版O(n2)

  1.  public int maxSubArray1(int[] nums) {
  3.         int maxSum=0;
  5.         for (int i = 0; i < nums.length; i++) {
  6.             int tempSum=0;
  8.             for (int j = i; j < nums.length; j++) {
  9.                 tempSum += nums[j];
  11.                 if (tempSum > maxSum) {
  12.                     maxSum=tempSum;
  13.                 }
  14.             }
  15.         }
  16.         return maxSum;
  17.     }

方法三：O(n)

  1. public int maxSubArray2(int[] nums) {
  3.         int maxSum=0;
  4.         int tempSum=0;
  6.         for (int i = 0; i < nums.length; i++) {
  7.             tempSum+=nums[i];
  9.             if (tempSum > maxSum) {
  10.                 maxSum=tempSum;
  11.             } else if (tempSum < 0) {
  12.                 tempSum=nums[i];
  13.             }
  14.         }
  15.         return maxSum;
  16.     }

方法四：leetCode题解

  1. public int maxSubArray4(int[] nums) {
  3.         int max = Integer.MIN_VALUE,sum=0;
  5.         for (int i = 0; i < nums.length; i++) {
  6.             if (sum<0)
  7.                 sum=nums[i];
  8.             else
  9.                 sum+=nums[i];
  10.             if (sum>max)
  11.                 max=sum;
  12.         }
  13.         return max;
  14.     }