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

相比较输出连续子数组最大和的数值情况，本题要求输出最大和对应的最长连续子数组。 在动态规划的基础上，再增加四个变量：（1）保存当前遍历位置子串首尾位置；（2）最大和子串首尾位置。只需要根据实际情况判断是否要更新，如何更新，为了输出最长连续子数组，需要在当前子串值等于之前记录的最大子串值时也进行更新

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        //动态规划
        int sum = array[0],num = array[0];
        //当前遍历位置子串首尾位置
        int start_tmp = 0, end_tmp = 1;
        //最大和子串首尾位置
        int start = 0, end = 1;
        for(int i = 1; i < array.length; i++){
            //数组中包含i位置的连续串最大值（比较当前数组值与之前累加值大小）
            if(array[i] > num + array[i]){
                num = array[i];
                start_tmp = i;
                end_tmp = i + 1;
            }else{
                num = num + array[i];
                end_tmp++;
            }
            //记录并更新当前遍历数组的最大子串和
            if(num > sum || (num == sum) && (end_tmp - start_tmp) > (end - start)){
                sum = num;
                start = start_tmp;
                end = end_tmp;
            }
        }
        return Arrays.copyOfRange(array,start,end);
    }
}