题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。
因为是O(N)的复杂度，因此需采用的DP的思想，记录下当前元素之和（为其最优状态，既最大），将其与目前所得的最大和比较，若大于则更新，否则继续。状态的累加遵循这个过程：如果当前和小于0，则放弃该状态，将其归零。
我的拙劣想法：
1.遇到负数是首先保存一些当前的和值sum到局部变量result。
2.如果加上负数之后sum值小于0。则从后面一个重新开始算。找第一个正数开始重新求和。
第一份拙劣代码，无参考纯自己写。
int[] arr={4,0,-3,10,-4,7,-2,5};
int sum=0;
int result=-100; //定义结果最小值
for(int i=0;i<arr.length;i++){
if(arr[i]>0){ //数值大于0，sum值增加
sum=sum+arr[i];
}else { //数值小于0
if(sum>result){ //更新result
result=sum;
}
if(sum+arr[i]>0){ //查看加上负数后是否小于0
sum=sum+arr[i]; //不小于0，继续往后加
}else { //小于0，把sum值重置0
sum=0;
}
}
}
if(sum>result){ //最后一次可能sum大于result
result=sum;
}
System.out.println("result="+result+" sum="+sum );
上面的算法可以优化下，把sum+arr[i]<0的情况sum=0那里改一下，这里应该改成寻找下一个正数才对。这样每个负数就不用进行两次对比，进行一次小于0的对比就可以了。
int[] arr={1, -2, 3, 10, -4, 7, 2, -5};
int sum=0;
int result=arr[0];
for(int i=1;i<arr.length;i++){
if(arr[i]>=0){
sum=sum+arr[i];
}else {
if(sum>result){
result=sum;
}
if(sum+arr[i] < 0){
while(i<arr.length && arr[i]<0){
i++;
}
sum=arr[i]; //寻找下一个正数，重新开始计算
}else {
sum=sum+arr[i];
}
}
}
if(sum>result){
result=sum;
}
System.out.println("result="+result);
但上面的程序在输入全是负数的时候跑不通。下面的程序可以
int[] arr={-9, -2, -3, 10, 5, -1,-2, 5};
int sum=arr[0];
int result=arr[0];
for(int i=1;i<arr.length;i++){
if(arr[i]>=0){
if(sum<0){
sum=arr[i]; //把sum重置为正数
}else {
sum=sum+arr[i];
}
}else {
if(sum>result){
result=sum;
}
if(sum+arr[i] < 0){
sum=arr[i]; //和为负数时，从该负数开始算
}else {
sum=sum+arr[i];
}
}
}
if(sum>result){
result=sum;
}
System.out.println("result="+result);
全为负数时，sum值都为单独一个负数。跟result比较，可以更新result。
关键思想是在遇到和为负数的时候，从这个负数开始算。但是遇到下一个数是正数的时候，把sum重置为这个正数。
上面的代码纯属自己写，标准答案还是看网上吧！！
http://www.cnblogs.com/aLittleBitCool/archive/2011/01/16/1936842.html
发现网上的标准答案还是简单多了。。。庸俗
直接加，边加边更新最大值。小于0，就直接重新加！！！！简单的要命
