Best Time to Buy and Sell Stocks III -- Leetcode

[Question]
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most TWO transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

[Analysis]
It is equivalent to make a partition on the given array, and get the best sum of max profit from each of the two sections. Scanning from left to right, we can get the best profit for buying-and-selling the stock between day 0-th and day i-th. Scanning from the right to left, we can get the best profit for buying-and-selling the stock between day i-th and last day. Add two "best profit" at day i-th, and find out the maximum -- that is the maximum profit we can get if two transactions are allowed.

O(N).

[Solution]


class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty() || prices.size()==1) return 0;

        vector<int> left_profit (prices.size(), 0);
        vector<int> right_profit(prices.size(), 0);
        int high=0, low=0;
   
        low = prices[0];
        for (int i=1; i< prices.size(); i++) {
            low = min(low, prices[i]);
            left_profit[i] = max( prices[i]-low, left_profit[i-1] );
        }
   
        high = prices.back();
        for (int i=prices.size()-2; i>=0; i--) {
            high = max(high, prices[i]);
            right_profit[i] = max( high - prices[i],  right_profit[i+1] );
        }
   
        int max_profit=0;
        for (int i=0; i< prices.size(); i++) {
            int sum = left_profit[i] + right_profit[i];
            max_profit = max(sum, max_profit);
        }
       
        return max_profit;
    }
};

Longest Sub-string without repeating characters

[Question]
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

[Analysis]
Dynamic programming. Define L(i) as, the longest sub-string without repeating characters and ending at index i. Go each L(i) and find the maximum L(i).

[Solution]
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
     
        int* count = new int[s.size()];
        int max_len;
        unordered_map<char, int> char_last_index;
     
        char_last_index[s[0]] = 0;
        max_len = count[0]=1;
        for (int i=1; i<s.size(); i++) {
            if (s[i-1]==s[i]) {
                count[i] = 1;
            }
            else {
                if ( char_last_index.find(s[i]) != char_last_index.end() ){
                    count[i] = min( count[i-1]+1, i-char_last_index[s[i]] );
                }
                else {
                    count[i] = count[i-1]+1;
                }
            }
            char_last_index[s[i]] = i;
            if (count[i]>max_len) {
                max_len = count[i];
            }
        }
        delete count;
        return max_len;
    }
};

Binary Tree Maximum Path Sum

[Question]
Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

[Analysis]
Define "maximum path to a given node" (MPN) as, the maximum path starts from a node under and ends at the node. The MPN(node) = max (node.val, node.val+MPN(node.left), node.val+MPN(node.right)).

The maximum path (P) via node N and with the sub-tree rooted by N will be,
         P(N) = (MPN( N.left )>0)?MPN(N.left):0 + N.val + (MPN(N.right)>0)?MPN(N.right):0)

So using post-order traversal, we can get all P(N) and find the maximum P(N).
                 

[Solution]


/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSumToNode(TreeNode *root, int& cur_max) {
        if (root==NULL) return 0;
        int leftMax = maxPathSumToNode(root->left, cur_max);
        int rightMax= maxPathSumToNode(root->right, cur_max);
     
        int maxPathToRoot = max( max(leftMax+root->val, rightMax+root->val), root->val );
        int maxPathViaRoot = ((leftMax>0)?leftMax:0)
                            + root->val
                            + ((rightMax>0)?rightMax:0);
     
        if (maxPathViaRoot > cur_max) {
            cur_max = maxPathViaRoot;
        }
        return maxPathToRoot;
    }
 
    int maxPathSum(TreeNode *root) {
        if (root==NULL) return 0;
        int max = root->val;
        maxPathSumToNode( root, max );
        return max;
    }
};