首页 > 专题系列 > Java解POJ > POJ 2479 Maximum sum [解题报告] Java
2013
11-11

POJ 2479 Maximum sum [解题报告] Java

Maximum sum

问题描述 :

Given a set of n integers: A={a1, a2,…, an}, we define a function d(A) as below:

Your task is to calculate d(A).

输入:

The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.

Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.

输出:

Print exactly one line for each test case. The line should contain the integer d(A).

样例输入:

1

10
1 -1 2 2 3 -3 4 -4 5 -5

样例输出:

13

温馨提示:

In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.

Huge input,scanf is recommended.

解题代码:

import java.io.BufferedReader;
 import java.io.InputStreamReader;

 public class Main {

     int t;
     int l;
     int[] a;
     String[] s;
     int[] left;
     int[] right;
     int max = 0;

     int temp;

     public Main() throws Exception {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         t = Integer.parseInt(read.readLine());
         for (int i = 0; i < t; i++) {
             read.readLine();
             l = Integer.parseInt(read.readLine());
             a = new int[l];
             left = new int[l];
             right = new int[l];
             s = read.readLine().split(" ");
             for (int j = 0; j < l; j++) {
                 a[j] = Integer.parseInt(s[j]);
             }
             search();
             System.out.println(max);
         }
     }

     public void search() {
         temp = a[0];
         left[0] = temp;
         for (int i = 1; i < l; i++) {
             if (temp < 0) {
                 temp = 0;
             }
             temp += a[i];
             if (temp > left[i - 1]) {
                 left[i] = temp;
             } else {
                 left[i] = left[i - 1];
             }
         }
         temp = a[l - 1];
         right[0] = temp;
         for (int i = l - 2, k = 1; i >= 0; i--, k++) {
             if (temp < 0) {
                 temp = 0;
             }
             temp += a[i];
             if (temp > right[k - 1]) {
                 right[k] = temp;
             } else {
                 right[k] = right[k - 1];
             }
         }
         max = left[0] + right[l - 2];
         for (int i = 0; i < l - 1; i++) {
             if (left[i] + right[l - i - 2] > max) {
                 max = left[i] + right[l - i - 2];
             }
         }
     }

     public int getLength(int m, int n) {
         max = Integer.MIN_VALUE;
         temp = 0;
         for (int i = m; i < n; i++) {
             temp += a[i];
             if (temp > max) {
                 max = temp;
             }
             if (temp < 0) {
                 temp = 0;
             }
         }
         return max;
     }

     public static void main(String[] args) throws Exception {
         new Main();
     } 
}

  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!