Problem Explanation:

The task is to find the contiguous subarray (a part of the array) that has the largest sum. Kadane’s Algorithm efficiently solves this problem in O(n) time complexity.

Kadane’s Algorithm:

Kadane’s Algorithm works by iterating through the array and maintaining two variables:

1. current_sum: Keeps track of the maximum sum of the subarray that ends at the current index.
2. maximum_sum: Tracks the maximum sum of any subarray encountered so far.

At each step, Kadane’s algorithm checks if it is better to:

• Add the current element to the existing subarray (i.e., current_sum + arr[i]), or
• Start a new subarray with the current element (arr[i]), depending on which one is larger.

Code Walkthrough:

#include <stdio.h>

int maxSubArray(int arr[], int size) {
    int current_sum = arr[0]; // Start with the first element
    int maximum_sum = arr[0]; // Initialize maximum_sum with the first element

    for (int i = 1; i < size; i++) {
        // Decide whether to add the current element to the existing subarray or start a new subarray
        if (current_sum + arr[i] > arr[i]) {
            current_sum = current_sum + arr[i];
        } else {
            current_sum = arr[i];
        }

        // Update the maximum_sum if the current_sum is greater
        if (current_sum > maximum_sum) {
            maximum_sum = current_sum;
        }
    }

    return maximum_sum; // Return the maximum subarray sum
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; // Example array
    int size = sizeof(arr) / sizeof(arr[0]); // Calculate the size of the array

    int max_sum = maxSubArray(arr, size); // Find the maximum subarray sum

    printf("Maximum Subarray Sum is %dn", max_sum); // Print the result

    return 0;
}

Explanation of the Code:

1. Initialization:

   • current_sum starts with the value of the first element, representing the sum of the subarray that ends at the first element.
   • maximum_sum also starts with the value of the first element, keeping track of the highest subarray sum encountered so far.

2. Iterate through the array:

   • From the second element onward, for each element arr[i], we check if adding it to the current subarray (current_sum + arr[i]) is better than starting a new subarray with just arr[i].
   • If adding it gives a higher sum, we update current_sum. Otherwise, we start a new subarray from arr[i].

3. Update the maximum sum:

   • After processing each element, we update maximum_sum if current_sum is greater than the current maximum_sum.

4. Final result:

   • After iterating through the entire array, maximum_sum will contain the sum of the maximum subarray.

Example Walkthrough:

For the input array:

arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}

Step-by-step, the algorithm works as follows:

• Start with current_sum = -2 and maximum_sum = -2.
• Iterate through the array:
  • i = 1: current_sum = max(1, -2 + 1) = 1, maximum_sum = max(1, -2) = 1
  • i = 2: current_sum = max(-3, 1 + -3) = -2, maximum_sum = max(1, -2) = 1
  • i = 3: current_sum = max(4, -2 + 4) = 4, maximum_sum = max(1, 4) = 4
  • i = 4: current_sum = max(-1, 4 + -1) = 3, maximum_sum = max(4, 3) = 4
  • i = 5: current_sum = max(2, 3 + 2) = 5, maximum_sum = max(4, 5) = 5
  • i = 6: current_sum = max(1, 5 + 1) = 6, maximum_sum = max(5, 6) = 6
  • i = 7: current_sum = max(-5, 6 + -5) = 1, maximum_sum = max(6, 1) = 6
  • i = 8: current_sum = max(4, 1 + 4) = 5, maximum_sum = max(6, 5) = 6

Final result: maximum_sum = 6, which is the sum of the subarray [4, -1, 2, 1].

Output:

Maximum Subarray Sum is 6

Time Complexity:

• O(n) where n is the size of the array. We iterate through the array once.

Space Complexity:

• O(1) because we are only using a constant amount of extra space for variables (current_sum and maximum_sum).

This is the optimal solution for the maximum subarray sum problem using Kadane’s Algorithm.