2013
11-11

Maximum sum

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

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;

public class Main {

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

int temp;

public Main() throws Exception {
System.in));
for (int i = 0; i < t; i++) {
a = new int[l];
left = new int[l];
right = new int[l];
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. 从前有个财主特无聊，钱多的花不完，想了个乐子。他在街上放了一个盆，说：谁要是一口痰能吐满一个盆，我就送他一坐房子。很多人试了都不成功，这时有一个人一口特浓的痰，把一个盆子都吐满了，财主看了很惊讶，就送了他一坐房子。可是他还觉得无聊，看着那盆装满浓痰的盆子

2. 给你一组数据吧：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。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

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