Maximum Subarray

一、题目描写叙述

就是求一个数组的最大子序列

二、思路及代码

首先我们想到暴力破解

public class Solution {
    public int maxSubArray(int[] nums) {
       int sum = Integer.MIN_VALUE;
       for(int i=0; i<nums.length; i++)
           for(int j=i+1; j<nums.length; j++) 
               sum = Math.min(nums[i]+nums[j], sum);

       return sum;
    }
}

果然TLE了。于是要找到合适的时间复杂度。所以再寻找时间复杂度小于N平方的。

所以我们想到既然要求最大子序列，那么我们在扫面累加数组元素时，推断之前的元素是否小于0。假设小于0。说明不用累加了，由于会“拖累”后边求和的值。于是演变成了动态规划问题。递推公式就是maxSum=Math.max(maxSum,curSumi)。

当中 curSumi 就是到第 i 个数字时最大的和值。

public class Solution {
    public int maxSubArray(int[] nums) {
       int sum = nums[0], maxSum = nums[0];
       for(int i=1; i<nums.length; i++) {
           if(sum < 0) sum = 0; //推断之前的sum能否够利用
           sum += nums[i];
           maxSum = Math.max(sum, maxSum);
       }
       return maxSum;
    }
}

Maximum Product Subarray

一、题目描写叙述

二、代码及思路

思路与上道题有所不同。这里要求是求乘积，那么乘积有个最简单的性质：负负得正；

那么假设套用上面那道题的思路，当前最小值假设是负值，假设下一个也是负值。就非常可能成为一个非常大的正值。

所以我们这里须要两个保存当前最小值和最大值的局部变量。

public class Solution {
    public int maxProduct(int[] nums) {
        int localMaxProduct = nums[0], localMinProduct = nums[0], maxProduct = nums[0]; 

        for(int i=1; i<nums.length; i++) {
            int copy_localMinProduct = localMinProduct;
            localMinProduct = Math.min(Math.min(nums[i]*copy_localMinProduct, nums[i]*localMaxProduct), nums[i]);
            localMaxProduct = Math.max(Math.max(nums[i]*copy_localMinProduct, nums[i]*localMaxProduct), nums[i]);
            maxProduct = Math.max(localMaxProduct, maxProduct);
        }
        return maxProduct;
    }
}