hduoj 1003

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1003

解题思路：最简单的方法是穷举并计算出所有的子序列和，第一次出现最大值的序列则为答案，不过是从一个元素开始，还是从全元素开始，结果并不一样，复杂度高而且也会导致wa的问题。更好的思路是使用动态规划，对问题进行拆解。

以 {6 -1 5 4 -7} 为例，本质上是求 max ({6 -1 5 4} + (-7) , -7)；{6 -1 5 4} 同理

package oj;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int totalLine = scanner.nextInt();//读取总行数
        for (int currentLineNo = 1; currentLineNo <= totalLine; currentLineNo++) {

            int totalCurrentLine = scanner.nextInt();//当前行序列数
            long[] currentLineSequence = new long[totalCurrentLine + 1];
            for (int index = 1; index <= totalCurrentLine; index++) {
                    currentLineSequence[index] = scanner.nextLong();//当前行序列
            }
            
            long[] currentSums = new long[totalCurrentLine + 1];
            Arrays.fill(currentSums, Long.MIN_VALUE);
            currentSums[1] = currentLineSequence[1];
            
            int startPosition = 1, endPosition = 1;
            long max = Long.MIN_VALUE;
            int finalStartPostition = startPosition, finalEndPostition = endPosition;
            
            for (int index = 1; index <= totalCurrentLine; index++) {
                    //如果我之前序列的最大和小于0，那就从我这开始
                if (currentSums[index - 1] < 0) {
                        currentSums[index] = currentLineSequence[index];
                    startPosition = endPosition = index;
                } else {
                        //否则屁颠得跟到它们后面，肯定比我自己大
                    currentSums[index] = currentSums[index - 1] + currentLineSequence[index];
                    endPosition++;
                }
                if (max < currentSums[index]) {
                    max = currentSums[index];
                    finalStartPostition = startPosition;
                    finalEndPostition = endPosition;
                }
            }
            System.out.println("Case " + (currentLineNo) + ":");
            System.out.println(max + " " + finalStartPostition + " " + finalEndPostition);
            if (currentLineNo != totalLine) { // 最后一个用例不输出空行
                System.out.println();
            }
        }
        scanner.close();
    }

}