# 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;            }};`

--

--

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