1+ /*
2+ * Problem: 53
3+ * Name: Maximum Subarray
4+ * Difficulty: Medium
5+ * Topic: Greedy
6+ * Link: https://leetcode.com/problems/maximum-subarray/
7+ */
8+
9+ #include < algorithm>
10+ #include < bits/stdc++.h>
11+ using namespace std ;
12+
13+ // Divide and Conquer
14+ // Time Complexity: O(n log n)
15+ // Space Complexity: O(1)
16+ int maxSubArrayDCHelper (vector<int >& nums, int left, int right);
17+ int maxSubArrayDC (vector<int >& nums){
18+ return maxSubArrayDCHelper (nums, 0 , nums.size ()-1 );
19+ }
20+ int maxSubArrayDCHelper (vector<int >& nums, int left, int right){
21+ if (left == right) {return nums[left];}
22+ int mid = left + (right - left) / 2 ;
23+ int currentSum = 0 ;
24+ int leftSum = 0 ;
25+ for (int idx = mid - 1 ; idx >= left; idx--){
26+ currentSum += nums[idx];
27+ if (currentSum > leftSum){
28+ leftSum = currentSum;
29+ }
30+ }
31+ currentSum = 0 ;
32+ int rightSum = 0 ;
33+ for (int idx = mid + 1 ; idx <= right; idx++){
34+ currentSum += nums[idx];
35+ if (currentSum > rightSum){
36+ rightSum = currentSum;
37+ }
38+ }
39+ return max (max (maxSubArrayDCHelper (nums, left, mid-1 ),
40+ maxSubArrayDCHelper (nums, mid+1 , right)),
41+ leftSum+nums[mid]+rightSum);
42+ }
43+
44+ // Kadane's Algorithm
45+ // Time Complexity: O(n)
46+ // Space Complexity: O(1)
47+ int maxSubArrayKadane (vector<int >& nums) {
48+ if (nums.empty ()) {return 0 ;}
49+ int maxSum = nums[0 ];
50+ int currentSum = 0 ;
51+ for (int cur = 0 ; cur < nums.size (); cur++){
52+ currentSum += nums[cur];
53+ if (currentSum > maxSum){
54+ maxSum = currentSum;
55+ }
56+ if (currentSum < 0 ) {
57+ currentSum = 0 ;
58+ }
59+ }
60+ return maxSum;
61+ }
0 commit comments