解题思路
1.动态规划，根据题意，推导动态转移方程，sum(i+1)=max(a[i+1],sum(i)+a[i+1])
2.动态转移过程中，需要记录的数据有，针对于每个位置i，求取sum、区间指针left和right
3.将过程中保存的数据，用节点Node保存（max、l、r）
4.当求取sum(i+1)过程中，max为sum(i)+a[i+1]时，left保持不变，right+1；当max为a[i+1]时，left与right变为i+1
5.将每个节点存在的最大值，排序，优先按照max、其次为max相同，优先为左区间，然后为右区间
解题遇到的问题
1.不同节点，很有可能有相同的最大值，所以此时需要对比这两个节点的区间，节点区间较小的节点为所求节点
2.部分测试用例和答案
8
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
3 -2 1 -2
3 -2 -2 -2
7 -3 5 -7 3 4 -1 5
4 -3 -5 -2 -1
3 -3 -2 -7
4 0 0 0 0
Case 1:
14 1 4
Case 2:
7 1 6
Case 3:
1 2 2
Case 4:
-2 1 1
Case 5:
11 4 7
Case 6:
-1 4 4
Case 7:
-2 2 2
Case 8:
0 1 1
后续需要总结学习的知识点
无
##解法1
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner mScanner = new Scanner(System.in);
// T(1<=T<=20)
int t = mScanner.nextInt();
int i = 1;
List<Node> list = new ArrayList<Node>();
while (i <= t) {
// N(1<=N<=100000)
// 动态规划，根据题意，推导动态转移方程，sum(i+1)=max(a[i+1],sum(i)+a[i+1])
list.clear();
int n = mScanner.nextInt();
BigInteger sum = mScanner.nextBigInteger();
int left = 1, right = 1;
// 将过程中保存的数据，用节点Node保存（max、l、r）
list.add(new Node(sum, left, right));
for (int j = 2; j <= n; j++) {
BigInteger ai1 = mScanner.nextBigInteger();
// 当求取sum(i+1)过程中，max为sum(i)+a[i+1]时，left保持不变，right+1；当max为a[i+1]时，left与right变为i+1
if (ai1.compareTo(sum.add(ai1)) == 1) {
sum = ai1;
left = j;
right = j;
} else {
sum = sum.add(ai1);
right = j;
}
list.add(new Node(sum, left, right));
}
// 将每个节点存在的最大值，排序，优先按照max、其次为max相同，优先为左区间，然后为右区间
Collections.sort(list, new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
if (o2.max.compareTo(o1.max) != 0) {
return o2.max.compareTo(o1.max);
} else {
if (o1.l != o2.l) {
return o1.l - o2.l;
} else {
return o1.r - o2.r;
}
}
}
});
// System.out.println(list);
Node node = list.get(0);
System.out.println("Case " + i + ":");
System.out
.println(node.max.toString() + " " + node.l + " " + node.r);
if (i != t) {
System.out.println();
}
i++;
}
mScanner.close();
}
}
/**
* 动态转移过程中，需要记录的数据有，针对于每个位置i，求取sum、区间指针left和right
*/
class Node {
BigInteger max;
int l;
int r;
public Node() {
}
public Node(BigInteger b, int le, int ri) {
max = b;
l = le;
r = ri;
}
@Override
public String toString() {
return max.toString() + " " + l + " " + r;
}
}
