本题使用一个常用技巧: 前后缀分解
该技巧的常用套路如下:
1. 求前缀数组
2. 求后缀数组
3. 枚举前后缀数组的分界点
对于本题,可以分解为求连续数组前缀和的最大值和, 求连续数组后缀和的最大值
可以定义如下:
dp1[i]: 从1~i从前往后枚举,以数字a[i]结尾的,连续和的最大值
dp2[i]: 从n~i从后往前枚举,以数字a[i]结尾的,连续和的最大值
maxLeft[i]: 从1~i从前往后枚举,前1~i个数字连续和的最大值
maxRight[i]: 从n~i从后往前枚举,后n~i个数字连续和的最大值
状态计算如下:
dp1[i] = max( dp1[i - 1] + a[i], a[i])
maxLeft[i] = max(maxLeft[i - 1], dp1[i])
dp2[i] = max( dp2[i + 1] + a[i], a[i])
maxRight[i] = max(maxRight[i + 1], dp2[i])
最后枚举前后缀数组的分界点
总体时间复杂度: O(N)
import java.io.*;
import java.util.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
static int N = 50010, INF = 10010;
static int[] a = new int[N], dp1 = new int[N], dp2 = new int[N], maxLeft = new int[N], maxRight = new int[N];
public static void main(String[] args) throws Exception{
int t = Integer.valueOf(read.readLine());
while(t -- > 0){
Arrays.fill(dp1, -INF); Arrays.fill(dp2, -INF);
Arrays.fill(maxLeft, -INF); Arrays.fill(maxRight, -INF);
int n = Integer.valueOf(read.readLine());
String[] ss = read.readLine().split(" ");
for(int i = 1; i <= n; i++) a[i] = Integer.valueOf(ss[i - 1]); //读取输入数组到a
for(int i = 1; i <= n; i++){ //处理前缀
dp1[i] = Math.max(dp1[i - 1] + a[i], a[i]);
maxLeft[i] = Math.max(maxLeft[i - 1], dp1[i]);
}
for(int i = n; i >= 1; i--) { //处理后缀
dp2[i] = Math.max(dp2[i + 1] + a[i], a[i]);
maxRight[i] = Math.max(maxRight[i + 1], dp2[i]);
}
int out = -INF;
//枚举前后缀的分界点
for(int i = 1; i <= n; i++){
out = Math.max(maxLeft[i - 1] + maxRight[i], out);
}
System.out.println(out);
}
}
}