//思路：
//贪心策略：遍历数组，到当前位置，上次保留的最大值如果为负数就要刷新一次，
// 即 curSum<=0时，当即果断丢弃，因为只会越加越小，刷新为当前值；
// 如果为正数，继续累加。

public int FindGreatestSumOfSubArray(int[] array) {
    if (array == null || array.length == 0){
        return 0;
    }
    int curSum = 0;
    int res= Integer.MIN_VALUE;
    for(int i=0;i<array.length;i++){
        if(curSum<=0){
            curSum = array[i];
        }else{
            curSum += array[i];
        }
        res = Math.max(res,curSum);
    }
    return res;
}

//思路：
// 贪心策略
// 假设第 i 轮进行卖出操作，买入操作价格应该在 i 之前并且价格最低。
public int maxProfit(int[] prices) {
    int n = prices.length;
    if(n==0 || n==1){
        return 0;
    }
    int minValue = prices[0];
    //初始时，不进行交易，当然收益为0
    int maxProfit  = 0 ;
    for(int i=1;i<n;i++){
        minValue = Math.min(minValue,prices[i]); //在 i 轮卖出前，以最低价格买入
        maxProfit = Math.max(maxProfit,prices[i]-minValue); //贪心策略：每轮都买出
    }
    return maxProfit;
}

// 思路：
// 贪心策略：每次选取最大的饼干给最“贪心"”的小朋友。
public int findContentChildren(int[] g, int[] s) {
    if(g==null || s==null){
        return 0;
    }
    Arrays.sort(g);
    Arrays.sort(s);
    int i=g.length-1;
    int j=s.length-1;
    int num=0;
    while (i>=0 && j>=0){
        if(s[j]>=g[i]){
            num++;
            j--;
        }
        i--;
    }
    return num;
}

// 思路：
// 贪心策略：
// 将最重的人和最轻的安排在同一艘船上
// 如果只能载一个人，则载最重的，如果剩下一个人，则只能单独趁一艘船。
public int numRescueBoats(int[] people, int limit) {
    if(people==null || people.length==0 || limit<=0){
        return 0;
    }
    Arrays.sort(people);
    int light=0;
    int heavy=people.length-1;
    int res=0;
    while (light<=heavy){
        if(light==heavy){ // 只剩下一个人，则单独一艘船
            res++;
            break;
        }
        if(people[light]+people[heavy]>limit){ // 如果只能载一个人，则载最重的
            res++;
            heavy--;
        }else{ // people[light]+people[heavy]<=limit，船可以搭载两个人
            res++;
            light++;
            heavy--;
        }
    }
    return res;
}

public List<String> summaryRanges(int[] nums) {
    List<String> res=new ArrayList<>();
    if(nums==null || nums.length==0){
        return res;
    }
    if(nums.length==1) {
        res.add(nums[0] + "");
        return res;
    }
    int start=nums[0];
    int end=start;
    for(int i=1;i<nums.length;i++){
        if(nums[i]==end+1){
            end++;
        }else{
            res.add(buildInterval(start,end));
            start=nums[i];
            end=start;
        }
    }
    res.add(buildInterval(start,end));
    return res;
}

private String buildInterval(int start,int end){
    if(start==end){
        return start+"";
    }
    return start+"->"+end;
}

// 思路：
// 首先计算最多能组成的不重叠区间个数，然后用区间总个数减去不重叠区间的个数。
// 其中区间结尾至关重要，选择的区间结尾越小，留给后面的空间就越大，那么后面能够选择的区间个数也就越大。
public int eraseOverlapIntervals(int[][] intervals) {
    if(intervals==null || intervals.length==0){
        return 0;
    }
    // 按照区间结尾进行升序排序
    // 写法一：比较器
    // 这里使用 p1[1]<p2[1]?-1:((p1[1]==p2[1])?0:1)，没有使用 p1[1]-p2[1]，这是因为两数相减存在溢出的情况
    /*Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] p1, int[] p2) {
                return p1[1]<p2[1]?-1:((p1[1]==p2[1])?0:1);
            }
        });*/
    // 写法二：使用正则表达式，
    Arrays.sort(intervals,
                (p1,p2)-> p1[1]<p2[1]?-1:((p1[1]==p2[1])?0:1));
    // 写法三：JDK8简化写法
    /*Arrays.sort(intervals, Comparator.comparingInt(p->p[1]));*/
    int cnt=1; // 记录最大不重叠区间数
    int end=intervals[0][1]; // 记录前一个不重叠区间结尾位置
    for(int i=1;i<intervals.length;i++){
        if(intervals[i][0]<end){ // 重叠区间，注意这里 [1,2]和[2,3]不算重叠区间
            continue;
        }
        cnt++;
        end=intervals[i][1];
    }
    return intervals.length-cnt;
}

// 思路：本质上就是计算不重叠的区间个数，注意这里[1,2]和[2,3]属于重叠区间
public int findMinArrowShots(int[][] points) {
    if(points==null || points.length==0){
        return 0;
    }
    // 按区间结尾位置从小到大排序
    // 写法一：比较器
    /*Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]<o2[1]?-1:(o1[1]==o2[1]?0:1);
            }
        });*/
    // 写法二：正则表达式
    //Arrays.sort(points,(o1,o2)->(o1[1]<o2[1]?-1:(o1[1]==o2[1])?0:1));
    // 写法三：JDK8 简化写法
    Arrays.sort(points,Comparator.comparingInt(o->o[1]));
    int res=1;
    int end=points[0][1];
    for(int i=1;i<points.length;i++){
        if(points[i][0]<=end){ // 注意这里[1,2]和[2,3]属于重叠区间
            continue;
        }
        res++;
        end=points[i][1];
    }
    return res;
}

public int[][] merge(int[][] intervals) {
    if(intervals==null || intervals.length==1){
        return intervals;
    }
    // 按照开始位置从小到大进行排序
    // 写法一：比较器
    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return (o1[0]<o2[0])?-1:o1[0]==o2[0]?0:1;
        }
    });
    // 写法二：Lambda 表达式
    /*Arrays.sort(intervals,(o1,o2)->
                o1[0]<o2[0]?-1:o1[0]==o2[0]?0:1);*/
    // 写法三：JDK8 简化写法
    /*Arrays.sort(intervals, Comparator.comparingInt(o->o[0]));*/
    List<int[]> intervalList=new ArrayList<>(); // 保存结果区间
    int[] cur=intervals[0]; // 记录当前重叠区间
    int m=intervals.length;
    for(int i=1;i<m;i++){
        if(cur[1]>=intervals[i][0]){ // cur.end >= next.start
            cur[1]=Math.max(cur[1],intervals[i][1]);
        }else{
            intervalList.add(cur);
            cur=intervals[i];
        }
        if(i==m-1){
            intervalList.add(cur);
        }
    }
    int[][] res=new int[intervalList.size()][2];
    for(int i=0;i<intervalList.size();i++){
        int[] interval=intervalList.get(i);
        res[i][0]=interval[0];
        res[i][1]=interval[1];
    }
    return res;
}