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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        if(array.length == 1) {
            return array ;
        }
        int tail[] = new int[array.length] ;//tail[i]记录以i元素结尾的连续数组最大和
        int len[] = new int[array.length] ;//len[i]记录以i元素结尾的最大和连续数组的长度
        //初始化
        tail[0] = array[0] ;
        len[0] = 1 ;
        //计算
        for(int i = 1 ; i < array.length ; i ++) {
            //注意：>=而不是>,即：若当前元素与前一个连续数组整合的值等于当前元素时，也要把前一个连续数组算入新的连续数组
            if(tail[i-1]+array[i] >= array[i]) {
                tail[i] =  tail[i-1]+array[i];
                len[i] = len[i-1]+1 ;
            } else {//小于的话，就当前元素单独构成一个连续数组
                tail[i] =  array[i];
                len[i] = 1 ;
            } 
        }
        int maxTail = 0 ;//最大和的连续数组的尾部索引
        int maxLen = 0 ;//最大和的连续数组的长度
        for(int i = 0 ; i < tail.length; i ++) {
            //大于的话直接取其长度；等于的话还要比较长度是否大一些
            if(tail[i] > tail[maxTail] || tail[i] == tail[maxTail] && len[i] >= maxLen){
                maxTail = i ;
                maxLen = len[i] ;
            }
        }
        int[] res = new int[maxLen] ;
        int arrayS = maxTail - maxLen + 1 ;
        for(int i = 0 ; i < res.length ; i ++,arrayS++) {
            res[i] = array[arrayS] ;
        }
        return res ;
    }
}