算法学习（1）寻找最大子序列和问题
题目描述
给定一个含整数的数组，找到其最大的子序列和，如果最大值为负数，则返回0。
例：A1，A2，A3，A4，其子序列的可能情况是：
- {A1，A2，A3，A4}
- {A1，A2，A3}
- {A1，A2}
- {A1}
- {A2，A3，A4}
- {A2，A3}
- {A2}
- {A3，A4}
- {A3}
- {A4}
注意：{A1，A3}不属于其子序列，即子序列一定是连续的某几个元素组成的。
例：-5，4，3，-9，12，1，-2；其最大子序列由{12，1}组成
方法1
学习算法的第一步，就是当你什么聪明的办法都想不出来的时候，你也要会用最笨的办法去解决，不管这个方法的时间复杂度和空间复杂度有多高，能写出一个可行的算法，你就算成功了。
static int maxSubSum1(int[] a) {
int maxSum = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++) {
int tempSum = 0;
for (int k = i; k < j; k++) {
tempSum += a[k];
}
if (tempSum > maxSum) {
maxSum = tempSum;
}
}
}
return maxSum;
}
说明：第一轮循环，从第1个元素开始，依次和第2个、第3个...相加，每加完一次，比较得到的值是否大于上一次保存的最大值，如果是，则更新maxSum
时间复杂度：O(N^3)
计算时间复杂度的一个小技巧：一个for循环，时间复杂度为O(N),两层嵌套的for循环，时间复杂度为O(N^2)，依次类推。即使某些for循环并不真正会循环N次
方法2
方法1最里面的for循环其实很没必要，我们只要做一点改进就能得到一个时间复杂度为O(N^2)的算法
static int maxSubSum2(int[] a) {
int maxSum2 = 0;
for (int i = 0; i < a.length; i++) {
int tempSum = 0;
for (int j = i; j < a.length; j++) {
tempSum += a[j];
if (tempSum > maxSum2) {
maxSum2 = tempSum;
}
}
}
return maxSum2;
}
方法3（分治策略）
分治策略在这里虽然不是表现最好的算法，但它在大部分情况下都是表现最好的。
解决问题的关键两步：1. 分 2. 治
分：将问题分解为两个子问题求解，得到每个子问题各自的最优解
治：在合并子问题的解时，可能需要补充某些条件，使得最后结果是整个问题的最优解
在本题中，我们首先要分析出，最大子序列和出现的位置：
- 出现在整个序列的左半部分
- 出现在整个序列的右半部分
- 出现在跨越中间值的中间部分
当最大子序列和出现在第3种情况时，要注意，此时的 最优解 != 左边最优解 + 右边最优解，而应该是 左边包含了左序列的右边界的最优解 + 右边包含了右序列的左边界的最优解
举个例子：{3，-2，12}，左序列得到最优解为3，右序列得到最优解为12，中间部分最优解是（3+（-2）+ 12）= 13，三者取最大值，返回13
用代码解释：
第一步：考虑分解子问题，这里采用递归法，先实现入口函数：
maxSubSumRec(a, 0, a.length - 1)
第二步：实现递归的Base case
static int maxSubSumRec(int[] a, int left, int right) {
if (left == right) {
return Math.max(a[left], 0);
}
}
第三步：”分“
int center = (left + right) / 2;
int maxLeftSubSum = maxSubSumRec(a, left, center); //左子问题的最大子序列和
int maxRightSubSum = maxSubSumRec(a, center + 1, right);//右子问题的最大子序列和
第四步：”治“，处理获取中间部分的最大序列和
int maxLeftBorderSum = 0, leftBorderSum = 0, maxRightBorderSum = 0, rightBorderSum = 0;
for (int i = center; i >= 0; i--) {
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
for (int i = center+1; i <= right; i++) {
rightBorderSum += a[i];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
第五步：返回三个值中的最大值
return max(maxLeftSubSum, maxRightSubSum, maxLeftBorderSum + maxRightBorderSum);
补充max方法实现：
public static int max(int... num) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < num.length; i++) {
if (num[i] > max) {
max = num[i];
}
}
return max;
}
所有代码：
static int maxSubSumRec(int[] a, int left, int right) {
if (left == right) {
return Math.max(a[left], 0);
}
int center = (left + right) / 2;
int maxLeftSubSum = maxSubSumRec(a, left, center);
int maxRightSubSum = maxSubSumRec(a, center + 1, right);
int maxLeftBorderSum = 0, leftBorderSum = 0, maxRightBorderSum = 0, rightBorderSum = 0;
for (int i = center; i >= 0; i--) {
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
for (int i = center+1; i <= right; i++) {
rightBorderSum += a[i];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
return max(maxLeftSubSum, maxRightSubSum, maxLeftBorderSum + maxRightBorderSum);
}
public static void main(String[] args) {
maxSubSumRec(a, 0, a.length - 1)
}
时间复杂度：二分的时间复杂度是O(logN)，在二分的里面嵌套了一层for循环，所以总的时间复杂度是O(NlogN)
方法四
方法四在这里可以得到最优的时间复杂度O(N)，且代码实现简洁，当然，代码层面表现的越简洁，写代码前的头脑风暴就越大。
分析最大子序列和的特点，我们发现最大子序列和的第一个元素一定不会是负值，因为如果第一个元素取了负值，那么总会存在一个和比它更大的子序列，并且，这个推论总是成立的
此时，我们做的事情非常简单，只要发现遍历到当前项时，得到的和小于0，那么我们直接抛弃这之前的所有项，我们发现，这时候我们通过一次遍历就可以完成这件事
static int maxSubSum4(int[] a) {
int maxSum = 0, tempSum = 0;
for (int i = 0; i < a.length; i++) {
tempSum += a[i];
if (tempSum > maxSum)
maxSum = tempSum;
else if (tempSum < 0) {
tempSum = 0;
}
}
return maxSum;
}
