算法/动态规划/MaxSum最大子序列和问题

问题描述

Problem Description
Given a sequence a[1],a[2],a[3]……a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output
For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Sample Output
Case 1:
14 1 4

Case 2:
7 1 6

思路一/枚举

选择一个起始点i，一个终点j，计算从i到j之间所有数的和sum，找到最大的赋给max。时间复杂度O(n^3)
java代码如下

public int maxSum1(int[] arr) {
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += arr[k];
                }
                max = sum > max ? sum : max;
            }
        }
        return max;
    }

对于上述算法，arr[i..j]其实可以用arr[i..j-1]来代替，因此可以优化得到时间复杂度为O(n^2)的过程
java代码如下：

public int maxSum2(int[] arr) {
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];
                max = sum > max ? sum :max;
            }
        }
        return max;
    }

思路二/动态规划

我们正常的想法可能是如果arr[i]>=0，那么我把它加入到max中。但是这样可能会产生问题，例如：arr[k]<0，但是后面有一个比 | arr[k] | 更大的数，可以抵消arr[k]带来的负效果，这样一来情况就变得复杂的多。

现在我们换一种想法，从arr[i]出发考虑。

我们设以arr[i]为结尾的最大和为sum[i]，例如在{2, -11, 4, -13, -5, -2}中，以-13为结尾的最大和sum[3]=-9，对应的子片段是{4, -13}。
arr[i]一定存在于sum[i]中，那么前面的arr[i-1]在不在里面呢——如果在，它必然是以sum[i-1]的形式存在，即sum[i] = max(sum[i–1]+a[i], a[i])，现在变成了sum[i-1]在不在sum[i]中的问题，简单判断sum[i-1]对sum[i]的作用是正面还是负面就ok啦^ ^
时间复杂度和空间复杂度都是O(n)。
java代码如下：

public int maxSum3(int[] arr) {
        int max = arr[0];
        int sum = 0;
        for (int anArr : arr) {
            if (sum > 0) {
                sum += anArr;
            } else {
                sum = anArr;
            }
            max = sum > max ? sum : max;
        }
        return max;
    }