53.Maximum Subarray

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.

解题思路一：求解最大子数组和，定义两个变量：maxsum 表示最大子数组和，cursum 表示当前最大和。cursum 初始化为 ，每次遍历数组中的元素，得到 cursum+nums[i] 和 nums[i] 中的最大值并赋值给 cursum（这样保证了 cursum 总能得到遍历到当前位置的最大和），然后再把 maxsum 和 cursum 中的最大值赋值给 maxsum。以此类推，数组遍历完成之后，maxsum 的值即为最大子数组和。

复杂度分析：需要遍历数组一次，时间复杂度为

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 （动态规划）来求解。

应用分治法（Divide and Conquer），类似二分查找，将数组分为两部分，分别找出左边和右边的最大子数组和，

复杂度分析：

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 开始，使得最大值为 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);
        
        // 利用快慢指针找到有序链表中点元素
        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;
    }
};