Day 87, ##, Reverse Words in a String, Maximum Product Subarray

Reverse Words in a String

Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
---------------------------------------------------------
另外可以用三步翻转法

class Solution {
public:
    void reverseWords(string &s) {
        string rt = "";
        
        for (int i = 0; i < s.length(); i++) {
            string word = "";
            while (i < s.length() && !isspace(s[i])) {
                word += s[i];
                i++;
            }
            if (word == "") continue;
            
            if (rt == "") {
                rt = word;
            }else {
                rt = word + " " + rt;
            }
            word = "";
            i--;
        }
        
        s = rt;
    }
};

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.
---------------------------------------------------------------
DP,dp[i] has the max(min) product subarray that ends at i
#1 can be optimized with two max and min variables
#2 can get rid of if condition, minDp = min(A[i],A[i] * minDp,A[i] * maxDp)

class Solution {
public:
    int maxProduct(int A[], int n) {
        vector<int> maxDp(n);
        vector<int> minDp(n);
        maxDp[0] = A[0];
        minDp[0] = A[0];
        
        int maxP = maxDp[0];
        int i = 1;
        while (i < n) {
            if (A[i] < 0) {
                minDp[i] = min(A[i],A[i] * maxDp[i - 1]);
                maxDp[i] = max(A[i],A[i] * minDp[i - 1]);
            }else {
                minDp[i] = min(A[i],A[i] * minDp[i - 1]);
                maxDp[i] = max(A[i],A[i] * maxDp[i - 1]);
            }
            maxP = max(maxP,maxDp[i]);
            i++;
        }
        
        return maxP;
    }
};

O(1) space

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int high = 1, low = 1;
        int maxSub = INT_MIN;
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) {
                high = max(nums[i],nums[i] * high);
                low = min(nums[i],nums[i] * low);
            }else {
                int th = high;
                high = max(nums[i],nums[i] * low);
                low = min(nums[i],nums[i] * th);
            }
            maxSub = max(maxSub,high);
        }
        
        return maxSub;
    }
};