题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

 

本题有四种不同时间复杂度的解法，

1.暴力求解法：时间复杂度o(n三次方)  

穷举所有子数组之和并找到最大值
（1）将给定数组的所有子数组列出来，然后找到子数组最大的情况。具体的，对数组内的每一个A[i]进行遍历，然后遍历以它们为
起点的子数组，比较各个子数组的大小，找到最大连续子数组。

 

2.优化上1的穷举，时间复杂度o(n的平方）

和1的方法唯一不同之处就是thisSum的位置不同，却在时间复杂度上有了很大的提升

 

 

3.分治法

将一个问题分解为两个子问题，然后分而解决之。

因为最大子序列和可能在三处出现，整个出现在数组左半部，或者整个出现在右半部，又或者跨越中间，占据左右两半部分。递归将左右子数组再分别分成两个数组，直到子数组中只含有一个元素，退出每层递归前，返回上面三种情况中的最大值。

具体步骤如下：

（1）先将数组分为两个等长的子数组a, b

（2）分别求出两个数组a，b的连续子数组之和

（3）还有一种情况（容易忽略）：有可能最大和的子数组跨越两个数组；

最后比较ma, mb, mc，取最大即可。

在计算mc时，注意：mc必定包含总区间的中间元素，因此求mc等价于从中间元素开始往左累加到最大值+从中间元素开始往右累加到最大值。

下述摘自《算法导论》：

 

注：

参考的很多代码写的都有问题，因为没有考虑到数组中的元素全为负数的情况，所以arr={-2,-8,-1,-5,-9}这样的情况，会报错。

所以在代码中加入了数组全为负数时的判断。

实现如下：

     

 

 

4.动态规划思想求解

针对这个问题，递推公式是DP[i]=max(DP[i-1]+A[i],A[i])，转移方程出来了，意味着写一层循环就可以解决这个问题。
当我们从头到尾遍历这个数组的时候，对于数组里的一个整数，它有两种选择：
（1）加入之前的SubArray；
（2）自己另起一个SubArray。
如果之前的SubArray的总体的和大于0的话，我们认为其对后续结果是有贡献的。这种情况下我们选择加入之前的SubArray。如果之前的SubArray的总体和为0或者小于0的话，我们认为其对后续结果是没有贡献的，甚至是有害的（小于0时）。这种情况下我们选择以这个数字开始，另起一个SubArray。

注意，上面代码第3行，为了防止全负的情况，thisSum，maxSum的初始值不能设为0.

思路一样，但是更简洁一点的代码：

实现1：

实现2：

 

和本题思路基本一致的leetcode：

121. Best Time to Buy and Sell Stock：

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

实现：

class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length==0||prices.length==1){
            return 0;
        }
        int[] diff=new int[prices.length-1];
        for(int i=1;i<prices.length;i++){
            diff[i-1]=prices[i]-prices[i-1];
        }
        int max=diff[0];
        int currSum=diff[0];
        for(int i=1;i<diff.length;i++){
            currSum=Math.max(currSum+diff[i],diff[i]);
            max=Math.max(currSum,max);
        }
        return max>0?max:0;
    }
}

参考：

1.https://www.cnblogs.com/lfeng1205/p/7504958.html

2.https://www.cnblogs.com/en-heng/p/3970231.html

3.https://www.cnblogs.com/allzy/p/5162815.html

4.《算法导论》