题解 | #连续子数组的最大和(二)#

/**

记录最大和的开始位置和结束位置就好啦，空间复杂度O(1),时间复杂度O(n)
**/
import java.util.*;
public class Solution {
    public int[] FindGreatestSumOfSubArray (int[] array) {
        int min = 0,max =0,maxsum=-101;
        for(int i=0,j=0,temp=-101;i<array.length;i++){
            if(temp+array[i]<array[i]){
                temp = array[i];
                j=i;
            }else{
                temp+=array[i];
            }
            if(temp>=maxsum){
                max =i;
                min = j;
                maxsum = temp;
            }   
        }
        int[] res = new int[max-min+1];
        for(int i=min;i<=max;i++)res[i-min]=array[i];
        return res;
    }
}