Product of Array Except Self

238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in O(n). For example, given [1,2,3,4], return [24,12,8,6].

Follow up: Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

S: DP 左右两遍扫描 要计算output[i]需要计算nums[1]..nums[i-1]的乘积，和nums[i+1]..nums[size-1]的乘积。左到右，右到左两边扫描即可。

    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size(), tmp = 1;
        if(size < 2) return vector<int>{};
        vector<int> output(size, 1);
        for(int i = 1; i < size; ++i){
            output[i] = output[i-1] * nums[i-1];
        }
        for(int i = size-1; i >= 0;--i){
            output[i] *= tmp;
            tmp *= nums[i]; 
        }
        return output;
    }

152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

S: DP

state: 对于以nums[i]结尾的subarray乘积的最大值curmax,最小值curmin. curmax[i]一定是curmax[i-1]nums[i],curmin[i-1]nums[i],nums[i]中最大的一个。curmin[i]同理。

    int maxProduct(vector<int>& nums) {
        if(nums.size() < 1) return 0;
        int result = nums[0], curmin = nums[0], curmax = nums[0];
        for(int i = 1; i < nums.size(); i++){
            int premax = curmax;
            curmax = max(curmax*nums[i], max(curmin*nums[i], nums[i]));
            curmin = min(premax*nums[i], min(curmin*nums[i], nums[i]));
            result = max(result, curmax);
        }
        return result;
    }

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

S1: DP O(N)

和上一题思路类似。state:curmax为以nums[i]结尾的subarray的和的最大值，curmax[i] = max(curmax[i-1]+nums[i]，nums[i])

    int maxSubArray(vector<int>& nums) {
        if(nums.size() < 1) return 0;
        int maxSum = nums[0], curmax = nums[0];
        for(int i = 1; i < nums.size(); ++i){
            curmax = max(nums[i], curmax+nums[i]);
            maxSum = max(maxSum, curmax);
        }
        return maxSum;
    }

S2: divide and conquer O(nlogn)

我们把数组分为两半。则最小子数组可能出现在左一半、或右一半（递归计算），或者被pivot穿过。对第三种情况，我们从pivot为右终点向前搜索最大数组，或从pivot为左终点向后搜索最大数组。

int maxSubArray(vector<int>& nums) {
    return maxSubArray_recur(nums, 0, nums.size());
}
int maxSubArray_recur(vector<int> &nums, int left, int right) {
    if (right == left+1) return nums[left];
    int mid = (left+right)/2;
    int ms1 = max(maxSubArray_recur(nums, left, mid), maxSubArray_recur(nums, mid, right));  
    int ms2l = INT_MIN, ms2r = INT_MIN;
    for (int k = mid-1, cumsum = 0; k>=left; --k) {
        cumsum += nums[k];
        ms2l = max(ms2l, cumsum);
    }
    for (int k = mid, cumsum = 0; k<right; ++k) {
        cumsum += nums[k];
        ms2r = max(ms2r, cumsum);
    }
    return max(ms2l+ms2r, ms1);
}