Maximum Sum Circular Subarray #dsa #interviewpreparation #coding #leetcodequestionandanswers

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i less than or equal to k1, k2 less than or equal to j with k1 % n == k2 % n.



Approach: Kadane's Algorithm

Use Kadane's algorithm to find the maximum subarray sum (max_sum) and the minimum subarray sum (min_sum) while keeping track of the total sum of the array. Then check if max_sum is positive, and if so, return the maximum of max_sum and (total_sum - min_sum) to handle non-circular subarrays. Otherwise, return max_sum as the maximum circular subarray sum.

Time Complexity: O(n)

Space Complexity: O(1)

#softwareengineer #dsa #interviewpreparation