Kadane's Algorithm

Definition:​

Kadane's Algorithm is an efficient algorithm to find the maximum sum of a contiguous subarray in an array of integers. It operates by iterating through the array while keeping track of the current subarray sum and the maximum sum encountered so far.

Video Explanation​

Watch

Characteristics:​

• Single-Pass Algorithm:
  The algorithm processes the array in a single pass:
  • It iteratively updates the maximum sum of the subarray ending at each position.
• Linear Time Complexity:
  The algorithm runs in O(N) time, where N is the number of elements in the array.
• Constant Space Complexity:
  It only requires a few extra variables, resulting in O(1) space complexity.

Time Complexity:​

• Best Case: $O(N)$
  The algorithm processes each element once during the traversal.
• Average Case: $O(N)$
  It consistently runs in linear time for any arrangement of elements.
• Worst Case: $O(N)$
  Regardless of the input distribution, the time complexity remains linear.

Space Complexity:​

• Space Complexity: $O(1)$
  The algorithm uses a constant amount of extra space.

Approach:​

The algorithm follows these steps:

1. Initialization:
   • Initialize two variables max_current and max_global with the value of the first element.
2. Traverse the Array:
   • For each element (starting from the second), update max_current as the maximum of the current element or the sum of max_current and the current element.
   • Update max_global to be the maximum of max_global and max_current.
3. Result:
   • max_global holds the maximum sum of the contiguous subarray.

C++ Implementation:​

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the maximum sum of a contiguous subarray
    int maxSubArray(vector<int>& nums) {
        int max_current = nums[0], max_global = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            // Update max_current to include current element or start fresh from current element
            max_current = max(nums[i], max_current + nums[i]);

            // Update max_global if the current subarray sum is higher
            max_global = max(max_global, max_current);
        }

        return max_global;
    }
};

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

    // Create an instance of Solution class
    Solution sol;

    // Find the maximum sum of the contiguous subarray
    int max_sum = sol.maxSubArray(nums);

    // Print the result
    cout << "The maximum sum of the contiguous subarray is: " << max_sum << endl;

    return 0;
}