题目描述：求连续子数组的最大和

输入：数组，输出最大和

  • 思路：计算所有连续子数组的和，比较并记录最大的值，暴力的解法时间复杂度O(N^3)
  • 动态规划，利用前一步计算的最大连续子序列的和来判断当前位置的最大连续子序列的和，时间,空间复杂度均为O(N)
  • dp[i]:当前0到i位置的最大连续子序列的和,如果{0,i-1}的最大连续子数组的和dp[i-1]是正数，则加上dp[i-1],否则
 public int FindGreatestSumOfSubArray(int[] array) {
        int len = array.length,sum = Integer.MIN_VALUE;
        int [] dp = new int[len];
        dp[0] = array[0];      
        for(int i=1;i<len;i++){
            dp[i] = dp[i-1] > 0 ? dp[i-1] + array[i] : array[i];          
            sum = Math.max(sum,curMax);
        }
        return sum;
    }

进阶版：省空间，用两个变量替代数组空间，时间复杂度为O(N),空间复杂度为O(1)

public int FindGreatestSumOfSubArray(int[] array) {
       
        int len = array.length,sum = Integer.MIN_VALUE,curMax=0, lastMax=0;
        lastMax = array[0];
        for(int i=1;i<len;i++){
            curMax = lastMax > 0 ? lastMax + array[i] : array[i];
            sum = Math.max(sum,curMax);
            lastMax = curMax;
        }
        return sum;
    }