HDU 1003 Max Sum

痛定思痛。 2022-06-17 00:38 91阅读 0赞

# **Max Sum** #

**Problem Description**

Given a sequence a\[1\],a\[2\],a\[3\]……a\[n\], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

**Input**

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

**Output**

For each test case, you should output two lines. The first line is “Case \#:”, \# means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

**Sample Input**

> 2  
> 5 6 -1 5 4 -7  
> 7 0 6 -1 1 -6 7 -5

**Sample Output**

> Case 1:  
> 14 1 4
> 
> Case 2:  
> 7 1 6

**Author**

Ignatius.L

**Code**

import java.util.Scanner;
    
    public class Main { 
    
        public static void main(String[] args) {
            Scanner s = new Scanner(System.in);
            int t = s.nextInt();
            for (int z = 0; z < t; z++) {
                int len = s.nextInt();
                int i = 1;
                int temp = s.nextInt();
                int pos1, pos2, x;
                pos1 = pos2 = x = 1;
                int maxSum, sum;
                maxSum = sum = temp;
                while (i < len) {
                    temp = s.nextInt();
                    i++;
                    if (sum + temp < temp) {
                        x = i;
                        sum = temp;
                    } else {
                        sum += temp;
                    }
                    if (sum > maxSum) {
                        maxSum = sum;
                        pos1 = x;
                        pos2 = i;
                    }
                }
                System.out.println("Case " + (z + 1) + ":");
                if (z != t - 1) {
                    System.out.println(maxSum + " " + pos1 + " " + pos2);
                    System.out.println();
                } else
                    System.out.println(maxSum + " " + pos1 + " " + pos2);
    
            }
        }
    }