连续子数组的最大和

￡神魔★判官ぃ 2022-06-09 03:37 161阅读 0赞

虽然在剑指offer上看到过，在真正做这道题的时候才发现自己的不足  
在线判题传送门：  
[点这里][Link 1]  
题目：  
一个数组有 N 个元素，求连续子数组的最大和。  
例如：\[-1,2,1\]，和最大的连续子数组为\[2,1\]，其和为 3。  
思路在代码里：

public class MaxSumInArray {
    
        public static void main(String[] args) {
            // 0 1 2 3 4 5 6 7 8 9
            int a[]={
       1,-2,3,10,-4,7,2,-19,2};
            // 8 10 11 2 12 
            int result = getMax(a);
            System.out.println(result);
        }
        //当和为正数时，temp继续往下加 因为就算加上负数，负数之后的正数也可能，弥补之前负数的损失
        //比如 3 -1 6 
        //和 3 2 8
        //但是会出现 加上的负数比较大的情况；所以要去掉这次的和 重新开始
        //比如 3 -5 9 
        //和 3 -2 7 你会发现加上 -2 还不如重新开始一行呢
        //所以判定 和为负数的时候temp重新开始
    
        public static int getMax(int[] a) {
            int max= a[0];
            int start=0;
            int end=0;
            int temp=max;   //用于保存某次的和
            int s =0;
            for(int i=1;i<a.length;i++){
                if(temp>0){
                    temp+=a[i];
                }else{
                    temp=a[i];
                    s=i;    //记录新开始的s，在满足temp》max时才进行交换
                }
                if(temp>max){
                    max=temp;
                    start=s;
                    end=i;    
                }
            }
            System.out.println(start+" "+end);
            return max;
        }
    
    }

[Link 1]: https://www.nowcoder.com/practice/5a304c109a544aef9b583dce23f5f5db?tpId=85&tqId=29858&tPage=2&rp=2&ru=/ta/2017test&qru=/ta/2017test/question-ranking