Maximum Subarray - C Solution

1. Introduction

In this blog post, we will explore a popular problem in array manipulation using C programming: finding the subarray with the largest sum in an array of integers. This problem is a classic example in dynamic programming and is crucial in areas like financial modeling and data analysis.

Problem

Given an integer array 'nums', the task is to find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

2. Solution Steps

1. Initialize two integer variables: maxSum (to store the maximum sum found so far) and currentSum (to store the current sum of the subarray).

2. Iterate through each element in the array.

3. Update currentSum by adding the current element. If currentSum becomes less than the current element, reset currentSum to the value of the current element.

4. Update maxSum if currentSum is greater than maxSum.

5. Return maxSum after the end of the loop.

3. Code Program

#include <stdio.h>

// Function to find the maximum sum of a subarray
int maxSubArray(int* nums, int numsSize) {
    int maxSum = nums[0], currentSum = nums[0];

    for (int i = 1; i < numsSize; i++) {
        currentSum = currentSum > 0 ? currentSum + nums[i] : nums[i];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }

    return maxSum;
}

// Main function to demonstrate maxSubArray function
int main() {
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; // Example input
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int result = maxSubArray(nums, numsSize); // Call the function
    printf("Output: %d\n", result); // Print the result
    return 0;
}

Output:

6

Explanation:

The program finds the largest sum of a contiguous subarray within the array [-2, 1, -3, 4, -1, 2, 1, -5, 4]. 

It uses an iterative approach to maintain the current sum of the subarray and the maximum sum found so far. The key is to reset the current sum to the current element if the sum becomes negative, as starting fresh can potentially lead to a larger sum. 

In the example, the subarray [4, -1, 2, 1] has the largest sum of 6. 

This method effectively solves the problem with a linear time complexity and demonstrates a fundamental technique in dynamic programming.