題目：輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)远荠。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組矮固，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的最大值譬淳。要求時(shí)間復(fù)雜度為O(n)档址。
例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2邻梆，因此輸出為該子數(shù)組的和18守伸。
因?yàn)槭荗(N)的復(fù)雜度，因此需采用的DP的思想浦妄，記錄下當(dāng)前元素之和（為其最優(yōu)狀態(tài)含友，既最大）替裆，將其與目前所得的最大和比較，若大于則更新窘问，否則繼續(xù)辆童。狀態(tài)的累加遵循這個(gè)過程：如果當(dāng)前和小于0，則放棄該狀態(tài)惠赫，將其歸零把鉴。

我的拙劣想法：
1.遇到負(fù)數(shù)是首先保存一些當(dāng)前的和值sum到局部變量result。
2.如果加上負(fù)數(shù)之后sum值小于0儿咱。則從后面一個(gè)重新開始算庭砍。找第一個(gè)正數(shù)開始重新求和。
第一份拙劣代碼混埠，無參考純自己寫怠缸。

        int[] arr={4,0,-3,10,-4,7,-2,5};
        int sum=0;
        int result=-100;        //定義結(jié)果最小值
        for(int i=0;i<arr.length;i++){
            if(arr[i]>0){                    //數(shù)值大于0，sum值增加
                sum=sum+arr[i];
            }else {                         //數(shù)值小于0
                if(sum>result){              //更新result
                    result=sum;
                }
                if(sum+arr[i]>0){            //查看加上負(fù)數(shù)后是否小于0
                   sum=sum+arr[i];        //不小于0钳宪，繼續(xù)往后加
                }else {                          //小于0揭北，把sum值重置0
                   sum=0;
                }
            }
        }
        
        if(sum>result){                      //最后一次可能sum大于result
            result=sum;
        }
        
        System.out.println("result="+result+" sum="+sum );

上面的算法可以優(yōu)化下，把sum+arr[i]<0的情況sum=0那里改一下吏颖，這里應(yīng)該改成尋找下一個(gè)正數(shù)才對(duì)搔体。這樣每個(gè)負(fù)數(shù)就不用進(jìn)行兩次對(duì)比，進(jìn)行一次小于0的對(duì)比就可以了半醉。

        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];        //尋找下一個(gè)正數(shù)疚俱，重新開始計(jì)算
                }else {
                    sum=sum+arr[i];
                }
                   
            }
               
        }
        if(sum>result){
            result=sum;
        }
        System.out.println("result="+result);

但上面的程序在輸入全是負(fù)數(shù)的時(shí)候跑不通。下面的程序可以

        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重置為正數(shù)
                }else {
                    sum=sum+arr[i];
                }
            }else {
                if(sum>result){
                    result=sum;
                }
                
                if(sum+arr[i] < 0){
                   sum=arr[i];             //和為負(fù)數(shù)時(shí)缩多，從該負(fù)數(shù)開始算
                }else {
                   sum=sum+arr[i];
                }
                   
            }
               
        }
        if(sum>result){
            result=sum;
        }
        System.out.println("result="+result);

全為負(fù)數(shù)時(shí)呆奕，sum值都為單獨(dú)一個(gè)負(fù)數(shù)。跟result比較衬吆，可以更新result登馒。

關(guān)鍵思想是在遇到和為負(fù)數(shù)的時(shí)候，從這個(gè)負(fù)數(shù)開始算咆槽。但是遇到下一個(gè)數(shù)是正數(shù)的時(shí)候，把sum重置為這個(gè)正數(shù)圈纺。

上面的代碼純屬自己寫秦忿，標(biāo)準(zhǔn)答案還是看網(wǎng)上吧！蛾娶！

http://www.cnblogs.com/aLittleBitCool/archive/2011/01/16/1936842.html
發(fā)現(xiàn)網(wǎng)上的標(biāo)準(zhǔn)答案還是簡單多了灯谣。。蛔琅。庸俗

直接加胎许，邊加邊更新最大值。小于0，就直接重新加９家ぁ９呈觥！穆碎！簡單的要命