309 codes updated.

liuyubobobo · liuyubobobo · commit d155572f928a · 2019-06-27T17:53:07.000-07:00
diff --git a/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/CMakeLists.txt b/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/CMakeLists.txt
@@ -1,7 +1,6 @@
-cmake_minimum_required(VERSION 3.5)
+cmake_minimum_required(VERSION 3.14)
 project(cpp_0309)
 
-set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+set(CMAKE_CXX_STANDARD 14)
 
-set(SOURCE_FILES main2.cpp)
-add_executable(cpp_0309 ${SOURCE_FILES})
+add_executable(cpp_0309 main.cpp)
diff --git a/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/main.cpp b/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/main.cpp
@@ -1,41 +1,57 @@
 /// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
 /// Author : liuyubobobo
-/// Time   : 2017-10-23
+/// Time   : 2019-06-27
 
 #include <iostream>
 #include <vector>
 
 using namespace std;
 
-/// Using hold and cash to trace the max money in different state
+
+/// Memory Search
 /// Time Complexity: O(n)
 /// Space Complexity: O(n)
 class Solution {
+
+private:
+    int n;
+
 public:
     int maxProfit(vector<int>& prices) {
 
-        if(prices.size() <= 1)
-            return 0;
+        n = prices.size();
+        if(n <= 1) return 0;
+
+        vector<int> buy(n, -1), sell(n, -1);
+        return _sell(prices, n - 1, buy, sell);
+    }
+
+private:
+    int _sell(const vector<int>& prices, int index, vector<int>& buy, vector<int>& sell){
+
+        if(index == 0) return 0;
+        if(index == 1) return max(0, prices[1] - prices[0]);
 
-        vector<int> hold(prices.size(), INT_MIN);
-        vector<int> cash(prices.size(), 0);
+        if(sell[index] != -1) return sell[index];
+        return sell[index] = max(_sell(prices, index - 1, buy, sell),
+                                 _buy(prices, index - 1, buy, sell) + prices[index]);
+    }
 
-        hold[0] = -prices[0];
-        hold[1] = max(hold[0], -prices[1]);
-        cash[1] = max(cash[0], hold[0] + prices[1]);
-        for(int i = 2 ; i < prices.size() ; i ++){
-            cash[i] = max(cash[i-1], hold[i-1] + prices[i]);
-            hold[i] = max(hold[i-1], cash[i-2] - prices[i]);
-        }
+    int _buy(const vector<int>& prices, int index, vector<int>& buy, vector<int>& sell){
 
-        return cash.back();
+        if(index == 0) return -prices[0];
+        if(index == 1) return max(-prices[0], -prices[1]);
+
+        if(buy[index] != -1) return buy[index];
+        return buy[index] = max(_buy(prices, index - 1, buy, sell),
+                                _sell(prices, index - 2, buy, sell) - prices[index]);
     }
 };
 
+
 int main() {
 
-    int prices1[] = {1, 2, 3, 0, 2};
-    vector<int> vec1(prices1, prices1 + sizeof(prices1)/sizeof(int));
+    vector<int> prices1 = {1, 2, 3, 0, 2};
     cout << Solution().maxProfit(vec1) << endl;
 
     return 0;
diff --git a/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/main2.cpp b/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/main2.cpp
@@ -1,38 +1,42 @@
 /// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
 /// Author : liuyubobobo
-/// Time   : 2017-10-24
+/// Time   : 2017-10-23
 
 #include <iostream>
 #include <vector>
 
 using namespace std;
 
-/// Using hold and cash to trace the max money in different state
+
+/// Dynamic Programming
 /// Time Complexity: O(n)
-/// Space Complexity: O(1)
+/// Space Complexity: O(n)
 class Solution {
 public:
     int maxProfit(vector<int>& prices) {
 
         if(prices.size() <= 1)
             return 0;
 
-        int hold[3] = {-prices[0], max(hold[0], -prices[1]), INT_MIN};
-        int cash[3] = {0, max(cash[0], hold[0] + prices[1]), 0};
+        vector<int> buy(prices.size(), 0);
+        vector<int> sell(prices.size(), 0);
 
+        buy[0] = -prices[0];
+        buy[1] = max(-prices[0], -prices[1]);
+        sell[1] = max(0, buy[0] + prices[1]);
         for(int i = 2 ; i < prices.size() ; i ++){
-            cash[i%3] = max(cash[(i-1)%3], hold[(i-1)%3] + prices[i]);
-            hold[i%3] = max(hold[(i-1)%3], cash[(i-2)%3] - prices[i]);
+            sell[i] = max(sell[i-1], buy[i-1] + prices[i]);
+            buy[i] = max(buy[i-1], sell[i-2] - prices[i]);
         }
 
-        return cash[(prices.size()-1)%3];
+        return sell.back();
     }
 };
 
+
 int main() {
 
-    int prices1[] = {1, 2, 3, 0, 2};
-    vector<int> vec1(prices1, prices1 + sizeof(prices1)/sizeof(int));
+    vector<int> prices1 = {1, 2, 3, 0, 2};
     cout << Solution().maxProfit(vec1) << endl;
 
     return 0;
diff --git a/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/main3.cpp b/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/main3.cpp
@@ -0,0 +1,42 @@
+/// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
+/// Author : liuyubobobo
+/// Time   : 2017-10-24
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Dynamic Programming with Space Optimization
+/// Time Complexity: O(n)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    int maxProfit(vector<int>& prices) {
+
+        int n = prices.size();
+
+        if(n <= 1)
+            return 0;
+
+        int buy[3] = {-prices[0], max(-prices[0], -prices[1]), 0};
+        int sell[3] = {0, max(0, prices[1] - prices[0]), 0};
+
+        for(int i = 2 ; i < n ; i ++){
+            sell[i % 3] = max(sell[(i - 1) % 3], buy[(i - 1) % 3] + prices[i]);
+            buy[i % 3] = max(buy[(i - 1) % 3], sell[(i - 2) % 3] - prices[i]);
+        }
+
+        return cash[(n - 1) % 3];
+    }
+};
+
+
+int main() {
+
+    vector<int> prices1 = {1, 2, 3, 0, 2};
+    cout << Solution().maxProfit(vec1) << endl;
+
+    return 0;
+}
