Create 053.Maximum-Subarray.cpp

wisdompeak · web-flow · commit ecf88f03c55e · 2020-09-23T22:20:46.000-07:00
diff --git a/Dynamic_Programming/053.Maximum-Subarray/053.Maximum-Subarray.cpp b/Dynamic_Programming/053.Maximum-Subarray/053.Maximum-Subarray.cpp
@@ -0,0 +1,18 @@
+class Solution {
+public:
+    int maxProduct(vector<int>& nums) 
+    {
+        long MAX = 1;
+        long MIN = 1;
+        long result =  INT_MIN;
+        
+        for (int i=0; i<nums.size(); i++)
+        {
+            long MAX_tmp = MAX, MIN_tmp = MIN;
+            MAX = max(max(MAX_tmp*nums[i],MIN_tmp*nums[i]),(long)nums[i]);            
+            MIN = min(min(MAX_tmp*nums[i],MIN_tmp*nums[i]),(long)nums[i]);
+            result = max(result,MAX);
+        }
+        return result;
+    }
+};
