We are given an array of n integers. We have to find the maximum non-empty contiguous subarray sum.
Naive Approach :
· We will check for every possible subarray and find the sum of that subarray.
· From all the subarrays possible we will take that sum which is maximum among them.
Code :
Time Complexity :
· Clearly, total number of operations done = n + (n-1) + …. + 1
= n*(n+1)/2
So, the time complexity is O(n^{2})
Approach :
· Let dp[i] denotes the maximum sum subarray ending at i^{th} index.
· Now, we will have only two possibilities :
(i) That subarray contains only 1 element ,i.e, value at i^{th} index
(ii) That subarray will contain the value at i^{th} index + maximum subarray ending at (i-1)^{th} index.
· Therefore, our recursive condition will be :
dp[i] = max(dp[i-1] + a[i], a[i]) , a is the array of given integers
· Now we need to find the maximum value among the dp array.
Code :
Time Complexity : O(n)
Applications :
Finding the maximum sum subarray by flipping the sign of a subarray, atmost once.
Approach :
· It’s obvious that we need to find the minimum sum subarray and then flip its sign.
· For finding the minimum sum subarray in O(n) time we can use Kadane’s algorithm. Method will be just the reverse of the described method.
Note : If the minimum sum subarray is greater than 0, then there is no need to change the sign because if we change then our value will decrease from the already given array sum.
Practice Problems :
https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0
https://www.codechef.com/problems/CDVNT01F
https://www.codechef.com/problems/KOL15B
Happy Coding 😊
By Programmers Army
Contributed by Shubham Kumar