题目描述：
一维数组中元素有正有负，求连续子向量的最大和。例如数组arr = {6,-3,-2,7,-15,1,2,2}，连续最大子向量和为8（从下标0开始下标3结束）。
分析
暴力解法
最直观的方法，暴力遍历，将所有可能的子集遍历一遍。但是存在的子数组有n(n+1)/2个，遍历一遍的时间复杂度为o(n^2)，对于大数据量肯定不行
一般解法
我们从头到尾将数组元素一个个往前加。定义两个变量int maxNum = 0当前最大和、int currSum = 0累加数组的和，然后开始遍历累加：
当累加数组的和currSum小于0时，则抛弃之前的和将当前数组元素赋值给currSum（因为假如之前的和为负数，那肯定拖累后面的和，不抛弃重头开始算肯定不可能是最大值，我们算的是连续子向量的最大和），当前最大和maxNum数值不变（第一步即数组下标0时maxNum=currSum）
当累加数组的和currSum大于0时，则将当前元素值累加到currSum，并currSum与maxNum进行比较
当currSum大于maxNum，则将maxNum=currSum；
当currSum小于maxNum，则maxNum不变
时间复杂度为O(n)
操作过程如下（{6,-3,-2,7,-15,1,2,2}）：
| 步骤 | 操作 | 累加的子数组和currSum | 最大的子数组和maxNum |
|---|---|---|---|
| 1 | 加6 | 6 | 6 |
| 2 | 加-3 | 3 | 3 |
| 3 | 加-2 | 1 | 1 |
| 4 | 加7 | 8 | 8 |
| 5 | 加-15 | -7 | 8 |
| 6 | 之前的和为-7，则直接抛弃前面的和，重新开始计算，加1 | 1 | 1 |
| 7 | 加2 | 3 | 3 |
| 8 | 加2 | 5 | 5 |
示例代码如下：
package com.example.demo;
public class Test5 {
public static void main(String[] args) {
int[] arr = new int[]{6,-3,-2,7,-15,1,2,2};
System.out.println(getMax( arr));
}
public static int getMax(int[] arr){
if(null == arr || arr.length <= 0){
return 0;
}
int maxNum= arr[0];
int currSum = arr[0];
for(int i = 1; i<arr.length; i++){
if(currSum > 0){
currSum += arr[i];
}else{
currSum = arr[i];
}
if(currSum > maxNum){
maxNum = currSum;
}
}
return maxNum;
}
}
动态规划，其实跟上面一样的
区别就在于每一步计算的累加的子数组和currSum用一个新的currSumArr数组保存了，每一次让currSumArr[i-1]来比较，跟上面是一模一样的
算法公式为：
max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] )
示例代码：
package com.example.demo;
public class Test6 {
public static void main(String[] args) {
int[] arr = new int[]{6,-3,-2,7,-15,1,2,2};
System.out.println(getMax( arr));
}
public static int getMax(int[] arr){
if(null == arr || arr.length <= 0){
return 0;
}
int maxNum= arr[0];
int[] currSumArr = new int[arr.length];
currSumArr[0] = arr[0];
for(int i = 1; i<arr.length; i++){
if(currSumArr[i-1] > 0){
currSumArr[i] = currSumArr[i-1] + arr[i];
}else{
currSumArr[i] = arr[i];
}
if(currSumArr[i] > maxNum){
maxNum = currSumArr[i];
}
}
return maxNum;
}
}
扩展
头条面试问题
100w用户，计算最大在线人数和时间段，已知用户的登陆时间和登出时间
例如：
2019-07-08 12:30:00 - 2019-07-08 13:30:00
2019-07-08 12:00:00 - 2019-07-08 14:30:00
2019-07-08 12:10:00 - 2019-07-08 14:10:00
……
思路：
其实上面的问题还是求连续子数组最大和问题（时间是连续线性的）
按计算当天为例（是计算一天还是一月只是单位不同，方法一样）
定义个长度为86400长度的整数数组（一天有这么多秒）用来存储每一秒用户变化登陆+1 登出-1，初始人数为0
则将数据初始入数组后，按公式max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] )便可求出当天最大在线人数是多少。
至于最大在线人数所在的时间段，其实就是该子数组的下标区间，修改一下dp数组的结构，记录一下每个和的子数组下标区间就可以了，例如dp结构改为：
dp[[当前子数组最大和，子数组最小下标，子数组最大下标]]
时间复杂度为o(n)
leetCode1109 航班预订统计问题
https://leetcode-cn.com/problems/corporate-flight-bookings/
参考：https://blog.csdn.net/kongmin_123/article/details/82430985