HDU-1003-（Max Sum）

解题思路

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;
    }
}