hduoj 1003

 费德  2018/02/03 13:51  210 次

题目链接 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();
    }

}

 作者:费德

少年费德的奇幻漂流

本博客如无特殊说明皆为原创,转载请注明来源:hduoj 1003

添加新评论