Kadane’s Algorithm

Understanding the Problem

The goal is to find the maximum sum of a contiguous subarray in a given array using Kadane's Algorithm.

Method 1: Kadane’s Algorithm

This method efficiently finds the maximum sum subarray in O(n) time.

#include <iostream>
#include <climits>
using namespace std;

int kadaneAlgorithm(int arr[], int n) {
    int maxSum = INT_MIN, currentSum = 0;
    for (int i = 0; i < n; i++) {
        currentSum += arr[i];
        if (currentSum > maxSum)
            maxSum = currentSum;
        if (currentSum < 0)
            currentSum = 0;
    }
    return maxSum;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum subarray: " << kadaneAlgorithm(arr, n);
    return 0;
}
            

Output:

Maximum sum subarray: 6

Method 2: Brute Force Approach

This method checks all possible subarrays and calculates their sums, leading to an O(n²) complexity.

#include <iostream>
#include <climits>
using namespace std;

int bruteForceMaxSubarray(int arr[], int n) {
    int maxSum = INT_MIN;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            if (sum > maxSum)
                maxSum = sum;
        }
    }
    return maxSum;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum subarray: " << bruteForceMaxSubarray(arr, n);
    return 0;
}
            

Output:

Maximum sum subarray: 6

Method 3: Divide and Conquer Approach

This method uses recursion to divide the array and find the maximum sum subarray.

#include <iostream>
#include <climits>
using namespace std;

int max(int a, int b) { return (a > b) ? a : b; }
int maxCrossingSum(int arr[], int l, int m, int h) {
    int sum = 0, leftSum = INT_MIN, rightSum = INT_MIN;
    for (int i = m; i >= l; i--) {
        sum += arr[i];
        if (sum > leftSum) leftSum = sum;
    }
    sum = 0;
    for (int i = m + 1; i <= h; i++) {
        sum += arr[i];
        if (sum > rightSum) rightSum = sum;
    }
    return max(leftSum + rightSum, max(leftSum, rightSum));
}

int maxSubArraySum(int arr[], int l, int h) {
    if (l == h) return arr[l];
    int m = (l + h) / 2;
    return max(maxSubArraySum(arr, l, m), max(maxSubArraySum(arr, m + 1, h), maxCrossingSum(arr, l, m, h)));
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum subarray: " << maxSubArraySum(arr, 0, n - 1);
    return 0;
}
            

Output:

Maximum sum subarray: 6