修改文件: DynamicProgram/121-best-time-to-buy-and-sell-stock.md

DragonFive · DragonFive · commit 58174c1326ca · 2017-06-15T11:03:54.000+08:00
diff --git a/DynamicProgram/121-best-time-to-buy-and-sell-stock.md b/DynamicProgram/121-best-time-to-buy-and-sell-stock.md
@@ -24,4 +24,23 @@ time out
                     result[i] = max(result[i],result[j] + prices[i] - prices[j]);
         return *max_element(result.begin(),result.end());
     }
+```
+
+## solution 2. Dp
+```cpp
+    int maxProfit(vector<int>& prices) {
+        if (prices.empty())
+            return 0;
+        vector<int> result(prices.size(),0);
+        int min_elem = 0;
+        for (int i = 1; i < prices.size(); i++)
+        {
+            if (prices[i] > prices[min_elem])
+                result[i] = result[min_elem] + prices[i] - prices[min_elem];
+            else
+                min_elem = i;
+        }
+        return *max_element(result.begin(),result.end());
+    }
+
 ```
