求子序列的最大和

题目

给定一个整数序列,其中包含正负数,求该序列中所有连续子序列的最大和。

要求时间复杂度为O(N)。

分析过程

假设int类型足够大到可以存储子序列和的最大值。

输入
①全为正数
②全为负数
③正负交替 a.负数在前b.正数在前

注:(零为可忽略项)

输出
① 一个正数 -> 输入 ① 全为正数 ② 正负交替
② 一个负数 -> 输入 ① 全为负数
③ 0 -> 输入 为 0

代码

package interview;

import org.junit.Test;

public class MaxSumSequence {
    @Test
    public void mainMaxSumSequence() {
        int[][] array1 = {
                {0}, {-1}, {1}, {-2, -3, -4}, {-22, -33, -44, -99},
                {-22, -33, -44, 100}, {-4, -33, 22},
                {-4, 33, 22}, {2, 3, 4}, {20, 30, 40},
                {20, -3, -4}, {20, -3, -4, -5}, {2, -3, -4, -5},
                {2, -3, 4, -5, 6}, {2, -3, 4, -5, 6, -9, 8},
                {2, -100, 44, -33, 44}, {2, -100, 44, -33, 44, -33, 77},
                {2, -100, 44, -33, 44, -33, 77, -100000},
                {101, -100, 44, -33, 44, -33, 77},
                {0, -100, 0, 300, 0, -299, 0, -500, 0, -300, 0, 600},
                {0, -100, 300, 0, -1000000, -500, -300, 600},
                {0, -100, 300, 0, -1, -500, -300, 600},
                {0, -100, 300, 0, -1, 500, -300, 600, -900},
                {0, -100, 300, 0, -1, -500, 301, -300, 600, -9}
        };
        for (int[] array : array1) {
            maxSum(array, 0, array.length);
        }

//        int[] array = {0, -100, 300, 0, -299, -500, -300, 600};
//        maxSum(array, 0, array.length);
    }

    public void maxSum(int[] array, int start, int len) {
        int tmp = 1 << 31;
        int sum = 0;
        System.out.print("初始化最小值为:" + tmp + "\t");

        for (int i = 0; i < array.length; ++i) {
            System.out.print(array[i] + ",");
            if (sum <= 0) {//①
                sum = array[i];
            } else {
                sum += array[i];
            }
            if (sum > tmp) {
                tmp = sum;
            }
        }
        System.out.println("\t最大子序列和为:" + tmp);
    }
}

输出

D:\pf\java\jdk1.8.0_181\bin\java.exe ...
Connected to the target VM, address: '127.0.0.1:55995', transport: 'socket'
初始化最小值为:-2147483648	0,	最大子序列和为:0
初始化最小值为:-2147483648	-1,	最大子序列和为:-1
初始化最小值为:-2147483648	1,	最大子序列和为:1
初始化最小值为:-2147483648	-2,-3,-4,	最大子序列和为:-2
初始化最小值为:-2147483648	-22,-33,-44,-99,	最大子序列和为:-22
初始化最小值为:-2147483648	-22,-33,-44,100,	最大子序列和为:100
初始化最小值为:-2147483648	-4,-33,22,	最大子序列和为:22
初始化最小值为:-2147483648	-4,33,22,	最大子序列和为:55
初始化最小值为:-2147483648	2,3,4,	最大子序列和为:9
初始化最小值为:-2147483648	20,30,40,	最大子序列和为:90
初始化最小值为:-2147483648	20,-3,-4,	最大子序列和为:20
初始化最小值为:-2147483648	20,-3,-4,-5,	最大子序列和为:20
初始化最小值为:-2147483648	2,-3,-4,-5,	最大子序列和为:2
初始化最小值为:-2147483648	2,-3,4,-5,6,	最大子序列和为:6
初始化最小值为:-2147483648	2,-3,4,-5,6,-9,8,	最大子序列和为:8
初始化最小值为:-2147483648	2,-100,44,-33,44,	最大子序列和为:55
初始化最小值为:-2147483648	2,-100,44,-33,44,-33,77,	最大子序列和为:99
初始化最小值为:-2147483648	2,-100,44,-33,44,-33,77,-100000,	最大子序列和为:99
初始化最小值为:-2147483648	101,-100,44,-33,44,-33,77,	最大子序列和为:101
初始化最小值为:-2147483648	0,-100,0,300,0,-299,0,-500,0,-300,0,600,	最大子序列和为:600
初始化最小值为:-2147483648	0,-100,300,0,-1000000,-500,-300,600,	最大子序列和为:600
初始化最小值为:-2147483648	0,-100,300,0,-1,-500,-300,600,	最大子序列和为:600
初始化最小值为:-2147483648	0,-100,300,0,-1,500,-300,600,-900,	最大子序列和为:1099
初始化最小值为:-2147483648	0,-100,300,0,-1,-500,301,-300,600,-9,	最大子序列和为:601
Disconnected from the target VM, address: '127.0.0.1:55995', transport: 'socket'

Process finished with exit code 0

今天在做这道题的时候,难在了①处,谨记思路一定要清晰,尽量避免忽冷忽热的环境。