{"post":"

Problem

Given an array of N integers. Find the contiguous sub-array with maximum sum.

Brute Force Approach

We will find the sum of all the subarrays and calculate the max, using two nested for loops.

#include<bits/stdc++.h>\r\nusing namespace std;\nvoid printLongestSumOfContinuousSubarray(int arr[], int arrSize){\r\nint sumGlobal = 0;\r\nfor(int i = 0; i < arrSize; i++){\r\nint sum = 0;\r\nfor(int j = i; j < arrSize; j++){\r\nsum += arr[j];\r\nsumGlobal = max(sumGlobal, sum);\r\n}\r\n}
\ncout&lt;&lt;\"Max Sum of contanuous subarray: \"&lt;&lt;sumGlobal;\n
\n}
\nint main(){\r\nint arr[] =  {-2, -3, 4, -1, -2, 1, 5, -3};\r\nint arrSize = sizeof(arr)/sizeof(arr[0]);\r\nprintLongestSumOfContinuousSubarray(arr, arrSize);\r\nreturn 0;\r\n}

TC – O(N²)

SC – O(1)

Optimal Approach

In optimized approach, we will use Kadane’s algorithm, We’ll keep a global maximum sum and a local maximum sum.

The local maximum sum at index i is the maximum of A[i] and the sum of A[i] and local maximum sum at index i-1.

#include<bits/stdc++.h>\r\nusing namespace std;\nvoid printLongestSumOfContinuousSubarray(int arr[], int arrSize){\r\nint localMax  = arr[0];\r\nint globalMax = arr[0];
\n  for(int i = 1; i &lt; arrSize; i++){\r\n    \tif(arr[i] &gt; localMax + arr[i]){\r\n\t\tlocalMax = arr[i];\r\n\t} else {\r\n\t\tlocalMax += arr[i];\r\n\t}\r\n      \r\n      \tif(localMax &gt; globalMax){\r\n\t\tglobalMax = localMax;\r\n\t}\r\n    }\r\n\r\ncout&lt;&lt;\"Max Sum of contanuous subarray: \"&lt;&lt;globalMax;\n
\n}
\nint main(){\r\nint arr[] =  {-2, -3, 4, -1, -2, 1, 5, -3};\r\nint arrSize = sizeof(arr)/sizeof(arr[0]);\r\nprintLongestSumOfContinuousSubarray(arr, arrSize);\r\nreturn 0;\r\n}

TC – O(N)

SC – O(1)

\n","title":"Maximum sum subarray | Kadane’s Algo","authorDetails":{"name":"studymite","slug":"admin"},"description":"Given an array of N integers. Find the contiguous sub-array with maximum sum. We will solve this problem with kadane's algorithm in O(N) time.","slug":"maximum-sum-subarray-kadanes-algo/","articleId":"636a83417bb1ce5072622b08","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}