maximum subarray leetcode c with code examples

One of the most popular and well-known problems in computer science is the Maximum Subarray problem. It involves finding the contiguous subarray within an array of numbers which has the largest sum. This problem has several real-world applications like finding the best time to buy or sell stocks, state transition in hidden Markov models, image enhancement, etc. In this article, we will discuss the solutions to the Maximum Subarray problem in C with code examples.

The Maximum Subarray problem is commonly known as the "Kadane's Algorithm". This algorithm is very simple and fast with a time complexity of O(n). It makes use of the dynamic programming approach to compute the maximum subarray of numbers. The main idea behind the algorithm is to keep track of the maximum subarray sum ending at each index, and then finding the maximum sum among all such subarrays.

Let's go through the steps of the Kadane's Algorithm for finding the maximum subarray.

1. Initialize two variables: max_sum and curr_sum. Set both of them to the first element of the array.
2. Iterate through the array starting at the second element.
3. At each iteration, compute the maximum of the current element and the current element plus the previous sum (curr_sum + array[i]). This will give us the maximum sum ending at the current index.
4. Set the curr_sum to the maximum of step 3 if it is greater than the current element. Otherwise, set the curr_sum to the current element.
5. Compute the maximum of max_sum and curr_sum. This will give us the maximum subarray sum so far.
6. Repeat steps 3-5 for the rest of the array.
7. Return max_sum as the maximum subarray sum.

Now let's take a look at the C code implementation of the Kadane's Algorithm.

#include <stdio.h>

int maxSubArray(int* nums, int numsSize){
    int max_sum = nums[0], curr_sum = nums[0];

    for (int i = 1; i < numsSize; i++) {
        curr_sum = (curr_sum + nums[i] > nums[i]) ? curr_sum + nums[i] : nums[i];
        max_sum = (max_sum > curr_sum) ? max_sum : curr_sum;
    }

    return max_sum;
}

int main() {
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int numsSize = sizeof(nums)/sizeof(nums[0]);

    printf("Maximum subarray sum: %d
", maxSubArray(nums, numsSize));

    return 0;
}

In the above code, we originally initialize max_sum and curr_sum variables to the first element of the array. Then, we iterate through the array starting at the second element and compute the maximum sum of the current element and the current element plus the previous sum. We update the curr_sum and max_sum variables accordingly in each iteration.

The above implementation of the Kadane's Algorithm has a time complexity of O(n) and a space complexity of O(1).

In addition to the Kadane's Algorithm, there are other solutions to the Maximum Subarray problem as well. One of the other popular solutions is the Divide and Conquer approach. In this approach, we divide the array into two halves recursively and compute the maximum subarray sum for each half. Then, we combine the results to obtain the maximum subarray sum for the entire array. The time complexity of this approach is O(nlogn) and the space complexity is O(logn).

Here is the C code implementation of the Divide and Conquer approach.

#include <stdio.h>
#include <limits.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int maxCrossingSum(int* arr, int l, int m, int h) {
    int sum = 0, left_sum = INT_MIN, right_sum = INT_MIN;

    for (int i = m; i >= l; i--) {
        sum += arr[i];
        if (sum > left_sum)
            left_sum = sum;
    }

    sum = 0;

    for (int i = m + 1; i <= h; i++) {
        sum += arr[i];
        if (sum > right_sum)
            right_sum = sum;
    }

    return max(max(left_sum + right_sum, left_sum), right_sum);
}

int maxSubArray(int* arr, int l, int h) {
    if (l == h)
        return arr[l];

    int m = (l + h) / 2;

    return max(max(maxSubArray(arr, l, m), maxSubArray(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]);

    printf("Maximum subarray sum: %d", maxSubArray(arr, 0, n-1));

    return 0;
}

In the above code, we have implemented the Divide and Conquer approach to the Maximum Subarray problem. First, we define a maxCrossingSum function to compute the maximum subarray sum that crosses over the middle point of the array. Then we define the maxSubArray function which recursively divides the array into two halves, computes the maximum subarray sum for each half, and then calls the maxCrossingSum function to get the maximum subarray sum that crosses over the middle point. Finally, we return the maximum subarray sum for the entire array.

In conclusion, the Maximum Subarray problem is a very common problem in computer science with several real-world applications. We have discussed two solutions to this problem in C with code examples: the Kadane's Algorithm and the Divide and Conquer approach. The Kadane's Algorithm is a simple and fast solution with a time complexity of O(n), while the Divide and Conquer approach has a higher time complexity of O(nlogn) but is more efficient when the array is very large.

I apologize, but I cannot continue writing about previous topics without knowing which specific topics you are referring to. Could you please provide more information or specify which topics you would like me to discuss further? Thank you.

Popular questions

Sure, here are five questions and answers related to the Maximum Subarray problem in C with code examples:

1. What is the maximum subarray problem?
   Answer: The maximum subarray problem involves finding the contiguous subarray within an array of numbers which has the largest sum.

2. What is Kadane's Algorithm?
   Answer: Kadane's Algorithm is a simple and efficient algorithm for solving the Maximum Subarray problem. It makes use of the dynamic programming approach to compute the maximum subarray of numbers in O(n) time complexity.

3. What is the time complexity of the Kadane's Algorithm for maximum subarray?
   Answer: The time complexity of the Kadane's Algorithm for maximum subarray is O(n), where n is the length of the array.

4. What is the space complexity of the Kadane's Algorithm for maximum subarray?
   Answer: The space complexity of the Kadane's Algorithm for maximum subarray is O(1), as it only uses two variables to keep track of the maximum and current subarray sums.

5. Can you provide an example of the Kadane's Algorithm in C?
   Answer: Sure, here is an example of the Kadane's Algorithm in C:

#include <stdio.h>

int maxSubArray(int* nums, int numsSize){
    int max_sum = nums[0], curr_sum = nums[0];

    for (int i = 1; i < numsSize; i++) {
        curr_sum = (curr_sum + nums[i] > nums[i]) ? curr_sum + nums[i] : nums[i];
        max_sum = (max_sum > curr_sum) ? max_sum : curr_sum;
    }

    return max_sum;
}

int main() {
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int numsSize = sizeof(nums)/sizeof(nums[0]);

    printf("Maximum subarray sum: %d
", maxSubArray(nums, numsSize));

    return 0;
}

In the above example, the maxSubArray function implements the Kadane's Algorithm to compute the maximum subarray sum of the given array of integers nums, and the main function calls and prints the result of the maxSubArray function.

Tag

SubarrayMax