修改文件: DynamicProgram/53-maximum-subarray.md

DragonFive · DragonFive · commit c198cd97f381 · 2017-06-16T09:56:30.000+08:00
diff --git a/DynamicProgram/53-maximum-subarray.md b/DynamicProgram/53-maximum-subarray.md
@@ -9,6 +9,7 @@ grammar_cjkRuby: true
 [53-maximum-subarray](https://leetcode.com/problems/maximum-subarray/#/description)
 
 # solution
+## 使用辅助空间+贪心法
 ```cpp
     int maxSubArray(vector<int>& nums) {
         //转移方程为，以当前节点结尾的最大的串，看前面的最大串的结果，如果为负数就算了。
@@ -24,4 +25,25 @@ grammar_cjkRuby: true
         }
         return *max_element(result.begin(),result.end());
     }
+```
+
+### 代码分析
+这里使用了辅助空间，空间复杂度为0(n);
+
+## 贪心算法
+
+```cpp
+    int maxSubArray(vector<int>& nums) {
+        //转移方程为，以当前节点结尾的最大的串，看前面的最大串的结果，如果为负数就算了。
+        if (nums.empty())
+            return 0;
+        int sum = nums[0];
+        int maxSum = nums[0];
+        for (int i = 1; i < nums.size(); i++)
+        {
+            sum=nums[i] += max(0, sum);
+            maxSum = max(sum, maxSum);
+        }
+        return maxSum;
+    }
 ```
