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

import java.util.*;

/**
 * NC166 连续子数组的最大和(二)
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // return solution1(array);
        return solution2(array);
        // return solution3(array);
    }

    /**
     * 前缀和 + 滑动窗口
     *
     * 超时!
     *
     * @param array
     * @return
     */
    private int[] solution1(int[] array){
        int len = array.length;

        int[] dp = new int[len+1];

        for(int i=1; i<=len; i++){
            dp[i] = dp[i-1] + array[i-1];
        }

        int max = Integer.MIN_VALUE;
        int left=0,right=len,sum;
        for(int gap=len; gap>0; gap--){
            for(int j=0; j+gap<=len; j++){
                sum = dp[j+gap] - dp[j];
                if(sum > max){
                    max = sum;
                    left = j;
                    right = j+gap;
                }
            }
        }

        int[] result = new int[right-left];
        for(int i=0,j=left; j<right; i++,j++){
            result[i] = array[j];
        }

        return result;
    }

    /**
     * 动态规划
     *
     * dp[i]表示以数组中第i个整数为结尾(必选)的最大和
     *
     *         { dp[i-1] + array[i-1]  , dp[i-1] >= 0
     * dp[i] = {
     *         { array[i-1]            , dp[i-1] < 0
     *
     * @param array
     * @return
     */
    private int[] solution2(int[] array){
        int len = array.length;

        int[] dp = new int[len+1];

        int index=1,width = 0;
        int maxSum = Integer.MIN_VALUE;
        int lastWidth = Integer.MIN_VALUE;
        for(int i=1; i<=len; i++){
            if(dp[i-1] >= 0){
                dp[i] = dp[i-1] + array[i-1];
                width++;
            }else{
                dp[i] = array[i-1];
                width = 1;
            }

            // 最大和更大
            if(dp[i] > maxSum){
                maxSum = dp[i];
                index = i;
                lastWidth = width;
            }
            // 最大和相同 且 长度更长
            else if(dp[i]==maxSum && width>lastWidth){
                index = i;
                lastWidth = width;
            }
        }

        int[] result = new int[lastWidth];
        for(int i=0,j=index-lastWidth; j<index; i++,j++){
            result[i] = array[j];
        }

        return result;
    }

    /**
     * 动态规划: 空间压缩
     *
     * pre 表示以数组中上一整数为结尾的最大和
     * curr表示以数组中当前整数为结尾的最大和
     *
     *        { pre + array[i-1]  , pre >= 0
     * curr = {
     *        { array[i-1]        , pre < 0
     *
     * @param array
     * @return
     */
    private int[] solution3(int[] array){
        int len = array.length;

        int index=1,width = 0;
        int maxSum = Integer.MIN_VALUE;
        int lastWidth = Integer.MIN_VALUE;
        int pre=0,curr;
        for(int i=1; i<=len; i++){
            if(pre >= 0){
                curr = pre + array[i-1];
                width++;
            }else{
                curr = array[i-1];
                width = 1;
            }

            // 最大和更大
            if(curr > maxSum){
                maxSum = curr;
                index = i;
                lastWidth = width;
            }
            // 最大和相同 且 长度更长
            else if(curr==maxSum && width>lastWidth){
                index = i;
                lastWidth = width;
            }

            pre = curr;
        }

        int[] result = new int[lastWidth];
        for(int i=0,j=index-lastWidth; j<index; i++,j++){
            result[i] = array[j];
        }

        return result;
    }
}