Day 15 of 31-Day May LeetCode Challenge

class Solution {
public:
int kadane(vector<int> arr, int n){
int dp[n];
dp[0] = arr[0];
for(int i=1;i<n;++i){
dp[i] = max(arr[i], dp[i-1]+arr[i]);
}
int max_sum = INT_MIN;
for(int i=0;i<n;++i){
max_sum = max(max_sum, dp[i]);
}
return max_sum;
}
int maxSubarraySumCircular(vector<int>& A) {

//method : using kadane's algorithm
//O(n) time & O(1) space
int n = A.size();

//STEP 1 : find maximum subarray sum in normal array
int max_kadane = kadane(A, n);


//STEP 2 : find maximum subarray sum in circular array
//maximum subarray sum in circular array = overall_sum - minimum subarray sum in normal array
//BUT instead of modifying kadane's() to find minimum subarray sum in normal array , INSTEAD
//we invert all elemets and then apply kadane() on array & ADD it to sum(instead of substracting)

int overall_sum = 0;
for(int i=0;i<n;++i) overall_sum += A[i];

for(int i=0;i<n;++i) A[i] *= -1;
int max_wrap = overall_sum + kadane(A, n);
//absolute values are considered to handle a corner case i.e when all array elements are negative
//in this case step 2 will always give 0 which may or may not be correct
return (abs(max_wrap)>abs(max_kadane))?max_wrap:max_kadane;

}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aanchal Patial

Aanchal Patial

13 Followers

We never really grow up, we only learn how to act in public