NC18题解 | #连续子数组的最大和#

动态规划:

解法1：时间复杂度为O(n) 解法2：空间复杂度为O(n)

空间复杂度为O(n)

public int get(int[] array){
        int n = array.length;
        int max = array[0];
        //dp[i]表示必须包含array[i]的连续数组的和
        int[] dp = new int[n];
        dp[0] = array[0];
        for(int i = 1; i < n; i++){
            dp[i] = Math.max(array[i],dp[i-1]+array[i]);
            max = Math.max(dp[i],max);
        }
        return max;
    }


空间复杂度为O(1):因为dp[i]每次更新只与dp[i-1]有关，与其他dp[?]无关

public int get(int[] array){
        int n = array.length;
        int max = array[0];
        //用一个变量temp替换掉dp[]  
        //dp[i]表示必须包含array[i]的连续数组的和
        int temp = array[0];
        dp[0] = array[0];
        for(int i = 1; i < n; i++){
            temp = Math.max(array[i],temp+array[i]);
            max = Math.max(temp,max);
        }
        return max;
    }