Kadane’s Algorithm

The "Kadane's algorithm" is a well-known algorithm used to find the maximum sum of a contiguous subarray within an array of numbers. It efficiently solves the "maximum subarray problem" and is named after its inventor, Jay Kadane.

The algorithm works by iteratively scanning the array from left to right, maintaining two variables: currentSum and maxSum. The currentSum variable keeps track of the sum of the subarray seen so far, while maxSum stores the maximum sum encountered during the traversal.

Here's an in-depth explanation of how Kadane's algorithm works:

Initialize currentSum and maxSum to the first element of the array.

currentSum = maxSum = array[0]

Iterate through the array from the second element (index 1) to the end.

For each element num at index i, calculate the new currentSum as the maximum value between:

num alone (starting a new subarray) or
num combined with the previous currentSum (extending the existing subarray).

currentSum = max(num, currentSum + num)

Update maxSum if the new currentSum is greater than the previous maxSum.

maxSum = max(maxSum, currentSum)

After iterating through the entire array, maxSum will hold the maximum sum of any contiguous subarray.

Return maxSum as the result.

The key idea behind Kadane's algorithm is the observation that, at each step, we only need to consider the maximum sum obtained by either starting a new subarray or extending the previous subarray. By keeping track of the maximum sum encountered so far (maxSum), we can find the overall maximum subarray sum efficiently.

The time complexity of Kadane's algorithm is O(n), where n is the size of the input array, as it involves a single pass through the array. The space complexity is O(1) since it uses only a constant amount of additional space to store the variables currentSum and maxSum.

Kadane's algorithm is a dynamic programming algorithm used to find the maximum subarray sum in a given array of integers. In C++, you can implement Kadane's algorithm using the following code:


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

int kadane(vector<int>& nums) {
    int n = nums.size();
    int max_sum = INT_MIN;
    int curr_sum = 0;

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

        if(curr_sum > max_sum)
            max_sum = curr_sum;

        if(curr_sum < 0)
            curr_sum = 0;
    }

    return max_sum;
}

int main() {
    int n;
    cin >> n;

    vector<int> nums(n);
    for(int i=0; i<n; i++)
        cin >> nums[i];

    int result = kadane(nums);
    cout << "The maximum subarray sum is " << result << endl;

    return 0;
}

In this code, the kadane() function takes a vector of integers nums as input and returns the maximum subarray sum. The function initializes three variables: n which is the size of the input array nums, max_sum which is initialized to the minimum value of integer, and curr_sum which is initialized to 0.

In the for loop, the function iterates through each element of nums and adds the element to curr_sum. Then, it checks if curr_sum is greater than max_sum. If it is, max_sum is updated to curr_sum.

Next, the function checks if curr_sum is less than 0. If it is, curr_sum is reset to 0, since any subarray containing a negative sum could not be the maximum subarray.

Finally, the function returns max_sum, which is the maximum subarray sum.

In the main() function, the user inputs the size of the array n and each element of the array nums. The kadane() function is then called to find the maximum subarray sum, which is outputted to the console.

Time Complexity: Kadane's algorithm has a time complexity of O(n), where n is the size of the input array. The algorithm performs a single pass through the array, visiting each element once. Therefore, the runtime grows linearly with the size of the input.

Space Complexity: The space complexity of Kadane's algorithm is O(1) or constant space. The algorithm only requires a few variables to keep track of the maximum sum and current sum. Regardless of the input array size, the algorithm uses a fixed amount of additional space, resulting in constant space complexity.

To summarize:

Time Complexity: O(n) (linear time)

Space Complexity: O(1) (constant space)

PRACTICE PROBLEMS :

Maximum Subarray