53.Maximum Subarray 2019-05-20

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

解題思路一：求解最大子數(shù)組和，定義兩個(gè)變量：maxsum 表示最大子數(shù)組和，cursum 表示當(dāng)前最大和。cursum 初始化為 ，每次遍歷數(shù)組中的元素，得到 cursum+nums[i] 和 nums[i] 中的最大值并賦值給 cursum（這樣保證了 cursum 總能得到遍歷到當(dāng)前位置的最大和），然后再把 maxsum 和 cursum 中的最大值賦值給 maxsum。以此類(lèi)推，數(shù)組遍歷完成之后，maxsum 的值即為最大子數(shù)組和。

復(fù)雜度分析：需要遍歷數(shù)組一次，時(shí)間復(fù)雜度為

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxsum = INT_MIN;
        int cursum = 0;
        for(int i = 0; i < nums.size(); i++){
            cursum = max(cursum+nums[i], nums[i]);
            maxsum = max(maxsum, cursum);
        }
        return maxsum;
    }
};

解題思路二：參考 FujiwaranoSai 的 Solution，采用 DP （動(dòng)態(tài)規(guī)劃）來(lái)求解。

應(yīng)用分治法（Divide and Conquer），類(lèi)似二分查找，將數(shù)組分為兩部分，分別找出左邊和右邊的最大子數(shù)組和，

復(fù)雜度分析：

121. Best Time to Buy and Sell Stock

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

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        if(prices.empty()){
            return 0;
        }
        
        int max_value = INT_MIN;
        int min_value = prices[0];
        
        // 從索引 0 開(kāi)始，使得最大值為 0
        for(auto i = 0; i < prices.size(); i++){
            max_value = max(max_value, prices[i] - min_value);
            min_value = min(min_value, prices[i]);
        }
        return max_value;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        if(prices.empty()){
            return 0;
        }
        
        int max_value = 0;
        int min_value = INT_MAX;
        
        for(auto i = 0; i < prices.size(); i++){
            max_value = max(max_value, prices[i] - min_value);
            min_value = min(min_value, prices[i]);
        }
        return max_value;
    }
};

122. Best Time to Buy and Sell Stock II

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 as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

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

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

123. Best Time to Buy and Sell Stock II

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return nullptr;
        if(!head->next) return new TreeNode(head->val);
        
        // 利用快慢指針找到有序鏈表中點(diǎn)元素
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* last = slow;
        
        while(fast->next && fast->next->next){
            last = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        
        fast = slow->next;
        last->next = nullptr;
        
        TreeNode* cur = new TreeNode(slow->val);
        
        if(head != slow){
            cur->left = sortedListToBST(head);
        }
        
        cur->right = sortedListToBST(fast);
        
        return cur;
    }
};