We are given an array `nums` and we need to return the maximum sum of a subarray in `nums`.\n\n---\n\n\u274C ***Solution - I (Brute-Force) [TLE]***\n\nWe can start with brute-force by trying out every possible sub-array in `nums` and choosing the one with maximum sum.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maxSubArray(vector& nums) {\n int n = size(nums), ans = INT_MIN;\n for(int i = 0; i < n; i++) \n for(int j = i, curSum = 0; j < n ; j++) \n curSum += nums[j],\n ans = max(ans, curSum); \n return ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maxSubArray(self, nums):\n ans = -inf\n for i in range(len(nums)):\n cur_sum = 0\n for j in range(i, len(nums)):\n cur_sum += nums[j]\n ans = max(ans, cur_sum)\n return ans\n```\n\n\n***Time Complexity :*** O(N²), where `N` is the number of elements in `nums`. There are `N*(N+1)/2` total sub-arrays and trying out each one takes time of O(N²)\n***Space Complexity :*** `O(1)`\n\n---\n\n\u274C ***Solution - II (Recursive) [TLE]***\n\nAnother way to consider every subarray and return the one that has maximum sum is using recursive approach. Here we can state the approach as -\n* At each index `i`, we can either pick that element or not pick it.\n* If we pick current element, then all future element must also be picked since our array needs to be contiguous.\n* If we had picked any elements till now, we can either end further recursion at any time by returning sum formed till now or we can choose current element and recurse further. This denotes two choices of either choosing the subarray formed from 1st picked element till now or expanding the subarray by choosing current element respectively.\n\nIn the code below, we will use `mustPick` to denote whether we must compulsorily pick current element. When `mustPick` is true, we must either return `0` or pick current element and recurse further. If `pickCur` is false, we have both choices of not picking current element and moving on to next element, or picking the current one.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maxSubArray(vector& nums) { \n return solve(nums, 0, false);\n }\n int solve(vector& A, int i, bool mustPick) {\n\t\t// our subarray must contain atleast 1 element. If mustPick is false at end means no element is picked and this is not valid case\n if(i >= size(A)) return mustPick ? 0 : -1e5; \n if(mustPick)\n return max(0, A[i] + solve(A, i+1, true)); // either stop here or choose current element and recurse\n return max(solve(A, i+1, false), A[i] + solve(A, i+1, true)); // try both choosing current element or not choosing\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maxSubArray(self, nums):\n def solve(i, must_pick):\n if i >= len(nums): return 0 if must_pick else -inf\n return max(nums[i] + solve(i+1, True), 0 if must_pick else solve(i+1, False))\n return solve(0, False)\n```\n\n***Time Complexity :*** O(N²), we are basically considering every subarray sum and choosing maximum of it. \n***Space Complexity :*** `O(N)`, for recursive space\n\n---\n\n\u2714\uFE0F ***Solution - III (Dynamic Programming - Memoization)***\n\nWe can observe a lot of repeated calculations if we draw out the recursive tree for above solution -\n\n```python\n f(0, False) \uD83D\uDD3D => repeated calculations\n\t\t\t\t\t / \\ \n \t\t f(1, False) f(1, True)\n\t\t\t / \\ \uD83D\uDD3D \\ \uD83D\uDD3D\n\t\t\t f(2, False) f(2, True) f(2, True)\n\t\t\t\t\t\t\t/ \\ \uD83D\uDD3D \\ \uD83D\uDD3D \\ \uD83D\uDD3D\n\t\t\t\t\t\tf(3, False) f(3,True) f(3, True) f(3, True)\n\t\t\t\t\t\t/ \\ \\ \\ \\\n\t\t\t\t ... ... ... ... ...\n```\n\nThese redundant calculations can be eliminated if we store the results for a given state and reuse them later whenever required rather than recalculating them over and over again. \n\nThus, we can use memoization technique here to make our solution more efficient. Here, we use a `dp` array where `dp[mustPick][i]` denotes the maximum sum subarray starting from `i` and `mustPick` denotes wheter the current element must be picked compulsorily or not.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maxSubArray(vector& nums) { \n vector> dp(2, vector(size(nums), -1));\n return solve(nums, 0, false, dp);\n }\n int solve(vector& A, int i, bool mustPick, vector>& dp) {\n if(i >= size(A)) return mustPick ? 0 : -1e5;\n if(dp[mustPick][i] != -1) return dp[mustPick][i];\n if(mustPick)\n return dp[mustPick][i] = max(0, A[i] + solve(A, i+1, true, dp));\n return dp[mustPick][i] = max(solve(A, i+1, false, dp), A[i] + solve(A, i+1, true, dp));\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maxSubArray(self, nums):\n @cache\n def solve(i, must_pick):\n if i >= len(nums): return 0 if must_pick else -inf\n return max(nums[i] + solve(i+1, True), 0 if must_pick else solve(i+1, False))\n return solve(0, False)\n```\n\n***Time Complexity :*** O(N), we are calculating each state of the `dp` just once and memoizing the result. Thus, we are calculating results for `2*N` states and returning them directly in future recursive calls.\n***Space Complexity :*** `O(N)`, for recursive space\n\n---\n\n\u2714\uFE0F ***Solution - IV (Dynamic Programming - Tabulation)***\n\nWe can employ similar logic in iterative version as well. Here, we again use `dp` array and use bottom-up approach. Here `dp[1][i]` denotes maximum subarray sum ending at `i` (including `nums[i]`) and `dp[0][i]` denotes maximum subarray sum upto `i` (may or may not include `nums[i]`). \n\nAt each index, we update `dp[1][i]` as max between either only choosing current element - `nums[i]` or extending from previous subarray and choosing current element as well - `dp[1][i-1] + nums[i]`\nSimilarly, `dp[0][1]` can be updated as max between maximum sum subarray found till last index - `dp[0][i-1]` or max subarray sum found ending at current index `dp[1][i]`.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maxSubArray(vector& nums) {\n vector> dp(2, vector(size(nums)));\n dp[0][0] = dp[1][0] = nums[0];\n for(int i = 1; i < size(nums); i++) {\n dp[1][i] = max(nums[i], nums[i] + dp[1][i-1]);\n dp[0][i] = max(dp[0][i-1], dp[1][i]);\n }\n return dp[0].back();\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maxSubArray(self, nums):\n dp = [[0]*len(nums) for i in range(2)]\n dp[0][0], dp[1][0] = nums[0], nums[0]\n for i in range(1, len(nums)):\n dp[1][i] = max(nums[i], nums[i] + dp[1][i-1])\n dp[0][i] = max(dp[0][i-1], dp[1][i])\n return dp[0][-1]\n```\n\nWe can actually do away with just 1 row as well. We denoted `dp[1][i]` as the maximum subarray sum ending at `i`. We can just store that row and calculate the overall maximum subarray sum at the end by choosing the maximum of all max subarray sum ending at `i`.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maxSubArray(vector& nums) {\n vector dp(nums);\n for(int i = 1; i < size(nums); i++) \n dp[i] = max(nums[i], nums[i] + dp[i-1]); \n return *max_element(begin(dp), end(dp));\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maxSubArray(self, nums):\n dp = [*nums]\n for i in range(1, len(nums)):\n dp[i] = max(nums[i], nums[i] + dp[i-1])\n return max(dp)\n```\n\n***Time Complexity :*** O(N), we are just iterating over the `nums` array once to compute the `dp` array and once more over the `dp` at the end to find maximum subarray sum. Thus overall time complexity is `O(N) + O(N) = O(N)`\n***Space Complexity :*** `O(N)`, for maintaining `dp`.\n\n---\n\n\u2714\uFE0F ***Solution - V (Kadane\'s Algorithm)***\n\nWe can observe that in the previous approach, `dp[i]` only depended on `dp[i-1]`. So do we really need to maintain the whole `dp` array of `N` elements? One might see the last line of previous solution and say that we needed all elements of `dp` at the end to find the maximum sum subarray. But we can simply optimize that by storing the max at each iteration instead of separately calculating it at the end.\n\nThus, we only need to maintain `curMax` which is the maximum subarray sum ending at `i` and `maxTillNow` which is the maximum sum we have seen till now. And this way of solving this problem is what we popularly know as **Kadane\'s Algorithm**\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maxSubArray(vector& nums) {\n int curMax = 0, maxTillNow = INT_MIN;\n for(auto c : nums)\n curMax = max(c, curMax + c),\n maxTillNow = max(maxTillNow, curMax);\n return maxTillNow;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maxSubArray(self, nums):\n cur_max, max_till_now = 0, -inf\n for c in nums:\n cur_max = max(c, cur_max + c)\n max_till_now = max(max_till_now, cur_max)\n return max_till_now\n```\n\n***Time Complexity :*** O(N), for iterating over `nums` once\n***Space Complexity :*** `O(1)`, only constant extra space is being used.\n\n*PS:* I have tried running `Solution - IV` and this solution multiple times and this solution, despite being `O(1)` shows higher memory usage(`28.8 MB` on average vs `28 MB` used by solution - IV) by LC consistently. If anyone can figure out the reason behind this, I will be happy to hear it out :)\n\n---\n\n\n\u2714\uFE0F ***Solution - VI (Divide & Conquer)***\n\nWe can solve this using divide and conquer strategy. This is the follow-up question asked in this question. This involves modelling the problem by observing that the maximum subarray sum is such that it lies somewhere -\n\n* entirely in the left-half of array `[L, mid-1]`, OR\n* entirely in the right-half of array `[mid+1, R]`, OR\n* in array consisting of mid element along with some part of left-half and some part of right-half such that these form contiguous subarray - [L\', R\'] = [L\', mid-1] + [mid] + [mid+1,R\'], where `L\' >= L` and `R\' <= R`\n\nWith the above observation, we can recursively divide the array into sub-problems on the left and right halves and then combine these results on the way back up to find the maximum subarray sum.\n\n```cpp\nclass Solution {\npublic:\n int maxSubArray(vector& nums) {\n return maxSubArray(nums, 0, size(nums)-1);\n }\n int maxSubArray(vector& A, int L, int R){\n if(L > R) return INT_MIN;\n int mid = (L + R) / 2, leftSum = 0, rightSum = 0;\n // leftSum = max subarray sum in [L, mid-1] and starting from mid-1\n for(int i = mid-1, curSum = 0; i >= L; i--)\n curSum += A[i],\n leftSum=max(leftSum, curSum);\n // rightSum = max subarray sum in [mid+1, R] and starting from mid+1\n for(int i = mid+1, curSum = 0; i <= R; i++)\n curSum += A[i],\n rightSum = max(rightSum, curSum); \n\t\t// return max of 3 cases \n return max({ maxSubArray(A, L, mid-1), maxSubArray(A, mid+1, R), leftSum + A[mid] + rightSum });\n }\t\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maxSubArray(self, nums):\n def maxSubArray(A, L, R):\n if L > R: return -inf\n mid, left_sum, right_sum, cur_sum = (L + R) // 2, 0, 0, 0\n for i in range(mid-1, L-1, -1):\n left_sum = max(left_sum, cur_sum := cur_sum + A[i])\n cur_sum = 0\n for i in range(mid+1, R+1):\n right_sum = max(right_sum, cur_sum := cur_sum + A[i])\n return max(maxSubArray(A, L, mid-1), maxSubArray(A, mid+1, R), left_sum + A[mid] + right_sum)\n return maxSubArray(nums, 0, len(nums)-1)\n```\n\n***Time Complexity :*** O(NlogN), the recurrence relation can be written as `T(N) = 2T(N/2) + O(N)` since we are recurring for left and right half (`2T(N/2)`) and also calculating maximal subarray including mid element which takes `O(N)` to calculate. Solving this recurrence using master theorem, we can get the time complexity as `O(NlogN)`\n***Space Complexity :*** `O(logN)`, required by recursive stack\n\n---\n\n\u2714\uFE0F ***Solution - VII (Optimized Divide & Conquer)***\n\nWe can further optimize the previous solution. The `O(N)` term in the recurrence relation of previous solution was due to computation of max sum subarray involving `nums[mid]` in each recursion. \n\nBut we can reduce that term to `O(1)` if we precompute it. This can be done by precomputing two arrays `pre` and `suf` where `pre[i]` will denote maximum sum subarray ending at `i` and `suf[i]` denotes the maximum subarray starting at `i`. `pre` is similar to `dp` array that we computed in dynamic programming solutions and `suf` can be calculated in similar way, just by starting iteration from the end.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n vector pre, suf;\n int maxSubArray(vector& nums) {\n pre = suf = nums;\n for(int i = 1; i < size(nums); i++) pre[i] += max(0, pre[i-1]);\n for(int i = size(nums)-2; ~i; i--) suf[i] += max(0, suf[i+1]);\n return maxSubArray(nums, 0, size(nums)-1);\n }\n int maxSubArray(vector& A, int L, int R){\n if(L == R) return A[L];\n int mid = (L + R) / 2;\n return max({ maxSubArray(A, L, mid), maxSubArray(A, mid+1, R), pre[mid] + suf[mid+1] });\n }\t\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maxSubArray(self, nums):\n pre, suf = [*nums], [*nums]\n for i in range(1, len(nums)): pre[i] += max(0, pre[i-1])\n for i in range(len(nums)-2,-1,-1): suf[i] += max(0, suf[i+1])\n def maxSubArray(A, L, R):\n if L == R: return A[L]\n mid = (L + R) // 2\n return max(maxSubArray(A, L, mid), maxSubArray(A, mid+1, R), pre[mid] + suf[mid+1])\n return maxSubArray(nums, 0, len(nums)-1)\n```\n\n***Time Complexity :*** O(N), the recurrence relation can be written as `T(N) = 2T(N/2) + O(1)` since we are recurring for left and right half (`2T(N/2)`) and calculating maximal subarray including mid element in `O(1)`. Solving this recurrence using master theorem, we can get the time complexity as `O(N)`\n***Space Complexity :*** `O(N)`, required by `suf` and `pre`.\n\n---\n\n\uD83D\uDCA1 **Note:**\n* The above divide and conquer solution works in `O(N)` but is **once you have calculated `pre` and `suf`, does it even make sense to go into divide and conquer approach?** I dont think divide and conquer approach after calculating `pre` & `suf`is useful, unless you Really want to solve it using **\u275DDivde and Conquer\u275E only**. You can instead do the following (which is similar to dp)- \n\n\t```cpp\n\tclass Solution {\n\tpublic:\n\t\tint maxSubArray(vector& nums) {\n\t\t\tvector pre = nums;\n\t\t\tfor(int i = 1; i < size(nums); i++) pre[i] += max(0, pre[i-1]);\n\t\t\treturn *max_element(begin(pre), end(pre));\n\t\t}\n\t};\n\t```\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---

Maximum Subarray

Problem Description

Problem Description

Answer Panel