aboutsummaryrefslogtreecommitdiff
path: root/other/max_subarray.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/max_subarray.cpp')
-rw-r--r--other/max_subarray.cpp32
1 files changed, 0 insertions, 32 deletions
diff --git a/other/max_subarray.cpp b/other/max_subarray.cpp
deleted file mode 100644
index 7356925..0000000
--- a/other/max_subarray.cpp
+++ /dev/null
@@ -1,32 +0,0 @@
-#include "leetcode.h"
-
-class Solution {
-public:
- int maxSubArray(vector<int> &nums) {
- return helper(nums, 0, nums.size() - 1);
- }
-
-private:
- int helper(vector<int> &nums, int l, int r) {
- if (l > r)
- return INT_MIN;
- int m = l + (r - l) / 2, mL = 0, mR = 0;
- int lMax = helper(nums, l, m - 1);
- int rMax = helper(nums, m + 1, r);
- for (int i = m - 1, sum = 0; i >= l; i--) {
- sum += nums[i];
- mL = max(sum, mL);
- }
- for (int i = m + 1, sum = 0; i <= r; i++) {
- sum += nums[i];
- mR = max(sum, mR);
- }
- return max(max(lMax, rMax), mL + mR + nums[m]);
- }
-};
-
-int main() {
- vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
- Solution obj;
- cout << obj.maxSubArray(nums);
-}