import java.util.*;
public class Solution {
    //[1,-2,3,10,-4,7,2,-5]
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length<=0) return 0;
        if(array.length==1) return array[0];
        //key代表数组的index,value代表和
        Map<Integer,Integer> map = new HashMap<>();
        List<Integer> midSum = new ArrayList<Integer>();
        for(int index=0;index<array.length;index++){
            //第一次
              if(map.isEmpty()){
                  if(array[index]<0) continue;
                  map.put(index,array[index]);
              }else{
                  if(map.get(index-1)+array[index]<0){
                      //如果连续和出现负数,存储之前和大于0的值,然后清空map,从下一个索引开始记录
                      midSum.add(map.get(index-1));
                      map.clear();
                  }else{
                      map.put(index,map.get(index-1)+array[index]);
                  }
                  
              }
        }
        
        //找到key中最大的value
        int res = 0-Integer.MAX_VALUE;
       
        if(map.isEmpty()){ 
            for(int i=0;i<array.length;i++){//特殊情况1:如果数组全是负数的话,返回最其中最大值
                if(array[i]>res) res = array[i];
            }
            for(Integer j:midSum) {//特殊情况2:【1,-2,1,2,-4,-4】
            	if(j>res) res=j;
            }
        }else{
            for(Integer temp:map.keySet()){//正常情况[1,-2,3,10,-4,7,2,-5]
                Integer tempValue = map.get(temp);
                if(tempValue>=res) res = tempValue;
            }
        }
        
        return res;
    }
}