A list of integer (either >= 0 or <0 in array A), please give on efficient program to find out 2 positions(start and end) and make the sum of the integers from A[start] to A[end] maximum, and return this value(maximum).
e.g. A[5]={2,-1,4,-3,2}; the sub list with start position "0" and end position "2" have the maximum sum "2+(-1)+4=5"
软件开发 编程题 算法题
------解决方案--------------------
1.首先start=第一个正数的下标，end=最末一个正数的下标(此步骤可以忽略)
2.然后从start开始累加，每步累加的值都保存下来，直到end
3.在保存下来的累加值中取最大值，end=此值对应的位置
4.然后从end开始累加，每步累加的值都保存下来，直到start
5.在保存下来的累加值中取最大值，start=此值对应位置，该最大值即为max
over
原理：
你想想，如果A[x]+...+A[x+m]>A[x]+...+A[x+n]
是否可以推出A[y]+...+A[y+m]>A[y]+...+A[y+n]呢？
所以，我们得出结论，对于连续累加，无论start为多少(定值)，产生最大sum的end是某个固定位置
反之，无论end为多少(定值)，产生最大sum的start为固定位置
这样，就变成了两个独立的“寻找位置”的任务了
对于上题，正向扫描为2 → 1 → 5 → 2 → 4，最大值在第3位，end=2
反向扫描为4 ← 2 ← 3 ← -1 ← 2，最大值在第1位，start=0
注：如果你扫描过程中发现多个最大值，说明他们都是可以的，例如-1，1，2，1，-1
这种情况下为了节省扫描次数，选用最小的end和最大的start
------解决方案--------------------
算是动态规划的一个经典题目吧：http://wenku.baidu.com/view/b1a18d114431b90d6c85c7be.html
------解决方案--------------------
public static void main(String[] args)
{
//初始化
List<Integer> list = Arrays.asList(new Integer[] {2, -1, 4, -3, 2});
System.out.println(list);
//辅助变量：当前起始下标，最大值的起始下标，最大值的结尾下标，当前求和，最大求和
int start, maxStart, maxEnd, sum, maxSum;
start = maxStart = maxEnd = sum = maxSum = 0;