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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        
        int[] sum1 = new int[array.length];
        sum1[0] = array[0]; 
        
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  // 记录和sum1[i]所对应的起始坐标low 
        int low = 0;                                                      // 开始时的起始坐标
        map.put(sum1[0], low);                                            
        int maxValue = array[0];                                          // 最大值
        for(int i = 1; i < array.length; i++){
            if(sum1[i - 1] >= 0){
                sum1[i] = sum1[i - 1] + array[i];                         // sum[i - 1] >= 0时，low不变
            }else {
                if(sum1[i - 1] + array[i] > array[i]){
                    sum1[i] = sum1[i - 1] + array[i];
                }else {
                    sum1[i] = array[i];
                    low = i;
                }
            }
            map.put(sum1[i],low);
            maxValue = maxValue > sum1[i] ? maxValue : sum1[i];
        }
        int high = sum1[0];                                             //取得最大值的终止坐标
        for(int ele = 0; ele < sum1.length; ele++){
            if(sum1[ele] == maxValue){
                high = ele;
            }
        }
        return Arrays.copyOfRange(array, map.get(maxValue), high + 1);
    }
}