Kadane's Algorithm:

Kadane's Algorithm is a dynamic programming technique used to find the maximum sum subarray in an array of integers (containing both positive and negative numbers) in O(n) time. It is a highly efficient solution to problems involving contiguous subarrays and their sums.

---

When to Use Kadane's Algorithm

Kadane's Algorithm is suitable for problems involving:

1. Finding Maximum Subarray Sum: Problems where you need to determine the largest sum possible from a contiguous subarray.

   • Example: Maximum Profit in a single interval of stock trading.

2. Finding Maximum Subarray Length (modified): If additional constraints like "maximum sum with fixed length" are needed.

3. Optimization Problems: Problems where maximizing or minimizing some value over a sequence is required, and the sequence can be split into subarrays.

---

Algorithm Steps

Kadane's Algorithm maintains two variables:

1. currentSum: Tracks the sum of the current subarray. This resets to 0 whenever it becomes negative.

2. maxSum: Keeps track of the maximum sum encountered so far.

   ---

   1. Maximum Subarray {>_}

      (LC 53)
      Given an array of integers, find the contiguous subarray with the largest sum.

      Approach:
      1️⃣ Use Kadane’s Algorithm to track the maximum subarray sum:

      • Add the current element to a running sum (currsum).

      • If currsum exceeds maxsum, update maxsum.

      • If currsum becomes negative, reset it to 0 (start a new subarray).
        2️⃣ Return the highest sum (maxsum) found.

Complexity:

• 🕒 Time: O(n) (Iterate through the array once).

• 🧠 Space: O(1) (No additional data structures).

        class Solution {
        public:
            int maxSubArray(vector<int>& nums) {
                int n = nums.size();
                int maxsum = INT_MIN; // Initialize with the smallest possible value
                int currsum = 0;

                for (int i = 0; i < n; i++) {
                    currsum += nums[i];

                    // Update maxsum if currsum is greater
                    if (currsum > maxsum) {
                        maxsum = currsum;
                    }

                    // Reset currsum to 0 if it becomes negative
                    if (currsum < 0) {
                        currsum = 0;
                    }
                }
                return maxsum;
            }
        };

2. Maximum Sum Circular Subarray {>_}

   (LC 918)
   Find the maximum sum of a subarray in a circular array (where the end of the array wraps back to the start).

   Approach:
   1️⃣ Case 1: Use Kadane’s Algorithm to find the maximum subarray sum (non-circular).
   2️⃣ Case 2: Find the "circular" maximum:

   • Compute the total sum of the array.

   • Use Kadane’s Algorithm to find the minimum subarray sum.

   • Subtract the minimum sum from the total sum to get the circular maximum.
     3️⃣ Edge Case: If all elements are negative, return the non-circular maximum (maxSum), as the circular case isn't valid.

Return: The maximum of maxSum (non-circular) and totalSum - minSum (circular).

Complexity:

• 🕒 Time: O(n) (Single pass for both cases).

• 🧠 Space: O(1) (No additional data structures).

        class Solution {
        public:
            int maxSubarraySumCircular(vector<int>& nums) {
                int n = nums.size();

                // Case 1: Maximum subarray sum using standard Kadane's algorithm
                int maxSum = INT_MIN, currMax = 0;
                for (int i = 0; i < n; i++) {
                    currMax += nums[i];
                    maxSum = max(maxSum, currMax);
                    if (currMax < 0) currMax = 0;
                }

                // Case 2: Maximum "circular" subarray sum
                int totalSum = 0, minSum = INT_MAX, currMin = 0;
                for (int i = 0; i < n; i++) {
                    totalSum += nums[i];
                    currMin += nums[i];
                    minSum = min(minSum, currMin);
                    if (currMin > 0) currMin = 0;
                }

                // If all numbers are negative, the circular case won't work
                if (totalSum == minSum) return maxSum;

                return max(maxSum, totalSum - minSum);
            }
        };