题目
对一个数组的一部分进行翻转（只能翻转依次），使得翻转后的数组能找到一个子数组，使子数组的和最大，求得到的最大和。
例如原数组 [-1, 3, -5, 2, -1, 3]，翻转第二个到第3个后得：[-1, -5, 3, 2, -1, 3]，此时有子数组 [3, 2, -1, 3] 的和最大，为 7。
思路：动态规划
- 两个 dp，第一个从左到右记录当前子数组的最大和，第二个从右到左记录当前子数组的最大和
- 遍历一遍，将两个 dp 的值相加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int[] dp1 = new int[n], dp2 = new int[n];
dp1[0] = arr[0];
dp2[n-1] = arr[n-1];
for (int i = 1; i < n; i++) {
dp1[i] = Math.max(dp1[i - 1], 0) + arr[i];
dp2[n -i-1] = Math.max(dp2[n - i], 0) + arr[n-i-1];
}
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp1[i] + dp2[i]);
}
System.out.println(res);
}
}
|