题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
LeetCode:53. 最大子序和
题解
显而易见的暴力解法
最容易想到的便是暴力穷举所有的子段和的开头，显而易见时间复杂度是O(n^2)。
代码：
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int n = nums.length;
for(int i = 0;i < n;i++){//穷举所有的开头
int thisSum = 0;
for(int j = i;j < n;j++){//穷举当前开头的子段和
thisSum += nums[j];
maxSum = Math.max(maxSum,thisSum);
}
}
return maxSum;
}
}
不是那么难的分治解法
本题也是分治解法应用的一个典型例子。“分”即将数组分为前后两段求解，“治”即分别求两段的最大子段和，“合”即比较两段的最大子段和和跨段的子段和，取最大值。
代码：
class Solution {
public int maxSubArray(int[] nums) {
return maxSub(nums, 0, nums.length - 1);
}
private int maxSub(int nums[], int left, int right){
if (left == right){
return nums[left];
}
int maxSum = 0;
int middle = (left + right) / 2;
int leftMaxSum = maxSub(nums, left, middle);//最半段最大子段和
int rightMaxSum = maxSub(nums, middle + 1, right);//右半段最大子段和
int leftRightSum = Integer.MIN_VALUE;//左半段以middle结尾的最大子段和
int rightLeftSum = Integer.MIN_VALUE;//右半段以middle+1开头的最大子段和
int thisLeftRightSum = 0;
int thisRightLeftSum = 0;
for(int j = middle;j >= left;j--){
thisLeftRightSum += nums[j];
leftRightSum = Math.max(leftRightSum,thisLeftRightSum);
}
for(int j = middle+1;j <= right;j++){
thisRightLeftSum += nums[j];
rightLeftSum = Math.max(rightLeftSum,thisRightLeftSum);
}
int crossMaxSum = leftRightSum + rightLeftSum;//跨段最大子段和
if(crossMaxSum>leftMaxSum&&crossMaxSum>rightMaxSum){
return crossMaxSum;
}else{
return Math.max(leftMaxSum,rightMaxSum);
}
}
}
时间复杂度分析：合的时间复杂度是O(n)，分的时间复杂度是2*T(n/2)。
则[T(n) = 2T(\frac{n}{2}) + O(n)]。根据主定理， θ(f(n)) = θ(n) ，[\log_b a = \log_2 2 = 1]，两者渐进复杂度相当，故时间复杂度为θ(nlogn)。
巧妙的动态规划
暴力解法穷举所有的开头，那么我们可不可以穷举所有的结尾？
对于数组中的任意一个元素，他要么是某个子段和的结尾，要么自己单独成为子段。因此后面的状态可以由前面的状态得出，可以使用动态规划。
代码：
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int thisSum = 0;
for(int i=0;i<nums.length;i++){
//如果已经求得的子段和加上当前元素比当前元素还小，说明前面求得的子段和没有意义
//那么子段和应更新为当前元素
thisSum = Math.max(nums[i],thisSum+nums[i]);
maxSum = Math.max(maxSum,thisSum);
}
return maxSum;
}
}
时间复杂度分析：只遍历一遍数组，时间复杂度为O(n)，辅助空间为常数空间O(1)。