本文共 3221 字，大约阅读时间需要 10 分钟。

题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 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。

题目分析

1. 我们发现以array[i]结束最大连续子数组和以array[i+1]结束的最大连续子数组有关系，因此其有最优子结构，我们可以考虑动态规划。设dp[i]表示以下标i为结尾的最大连续子数组，那么dp[i+1] = max(dp[i] + array[i+1],array[i+1])。代码如下：

public class Solution {       public int FindGreatestSumOfSubArray(int[] array) {           //dp[i]表示以dp[i]结束的最大连续子序列的和        //dp[i+1] = max(dp[i]+ array[i+1],array[i+1])        if(array.length == 0) {               return -1;        }        int[] dp = new int[array.length];        //初始化dp        dp[0] = array[0];        for(int i = 0; i < array.length-1; i++) {               dp[i+1] = Math.max(dp[i] + array[i+1],array[i+1]);        }        int max = Integer.MIN_VALUE;        for(int i = 0; i < array.length; i++) {               if(max < dp[i]) {                   max = dp[i];            }        }        return max;    }}

时间复杂度为o(n)，空间复杂度为o(n)。

2. 贪心算法。 算法时间复杂度O（n），空间复杂度为o(1),用total记录累计值，maxSum记录和最大值。
   基于思想：对于一个数A，若是A的左边累计数非负，那么加上A能使得值不小于A，认为累计值对整体和是有贡献的。如果前几项累计值负数，则认为有害于总和，total记录当前值。
   此时 若和大于maxSum 则用maxSum记录下来

public class Solution {       public int FindGreatestSumOfSubArray(int[] array) {           //dp[i]表示以dp[i]结束的最大连续子序列的和        //dp[i+1] = max(dp[i]+ array[i+1],array[i+1])        if(array.length == 0) {               return -1;        }        //返回值       int max = Integer.MIN_VALUE;       //表示连续和        int sum = 0;        for(int i = 0; i < array.length; i++) {               if(sum < 0) {               //这里注意重置sum = array[i]，而不是sum = 0,这是因为如果sum小于0，而array[i]>0,此时就会错过这个元素。                sum = array[i];            } else {                   sum+=array[i];            }            if(sum > max) {                   max = sum;            }                    }        return max;}}

3. 分治法。
   我们把数组从中间分成两个部分，那么最大连续子数组有三种情况：
   第一种：最大连续子数组包含中间的元素
   第二种：最大连续子数组在中间元素的左边
   第三种：最大连续子数组在中间元素的右边

import java.util.*;public class Solution {       /**     * max sum of the subarray     * @param arr int整型一维数组 the array     * @return int整型     */     public int maxsumofSubarray(int[] arr) {           return findMax(arr, 0, arr.length - 1);    }    public int findMax(int[] arr, int begin, int end) {           if(begin > end) {               return 0;        }        if (begin == end) {               return arr[begin];        }        int mid = (begin + end) / 2;        //找左边最大值        int leftMax = Integer.MIN_VALUE;        int left = mid-1;        int leftSum = 0;        while (left >= begin) {               leftSum += arr[left];            leftMax = Math.max(leftMax, leftSum);            left--;        }        //找右边的最大值        int rightMax = Integer.MIN_VALUE;        int right = mid + 1;        int rightSum = 0;        while (right <= end) {               rightSum += arr[right];            rightMax = Math.max(rightMax, rightSum);            right++;        }        int m = arr[mid];        if(leftMax > 0) {               m+=leftMax;        }        if(rightMax > 0) {               m+=rightMax;        }        int max1 = findMax(arr, begin, mid-1);        int max2 = findMax(arr, mid + 1, end);        max1 = Math.max(max1, max2);        return Math.max(m, max1);    }}