# Day 15 of 31-Day May LeetCode Challenge

--

Given a **circular array** **C** of integers represented by `A`

, find the maximum possible sum of a non-empty subarray of **C**.

Here, a *circular array* means the end of the array connects to the beginning of the array. (Formally, `C[i] = A[i]`

when `0 <= i < A.length`

, and `C[i+A.length] = C[i]`

when `i >= 0`

.)

Also, a subarray may only include each element of the fixed buffer `A`

at most once. (Formally, for a subarray `C[i], C[i+1], ..., C[j]`

, there does not exist `i <= k1, k2 <= j`

with `k1 % A.length = k2 % A.length`

.)

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;

}

};