Maximum Subarray In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement:

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

Example:

Input:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output:

6

Explanation: The subarray with the largest sum is [4, -1, 2, 1], which has a sum of 6.

Approach:

This problem can be solved using Dynamic Programming. The key idea is to compute the maximum sum subarray that ends at each index and update the global maximum. We will use the following approach:

1. Initialization:
   • Initialize two variables:
     • current_sum: This tracks the sum of the current subarray.
     • max_sum: This stores the largest sum encountered so far.
2. Iterate through the array:
   • For each element in the array, update current_sum to be the maximum of either:
     • The element itself (starting a new subarray).
     • The element added to the current_sum (continuing the current subarray).
   • Update max_sum if current_sum is greater than the current max_sum.
3. Time Complexity:
   • Time Complexity: O(n), where n is the number of elements in the array.
   • Space Complexity: O(1), since we are only using a constant amount of extra space.

Algorithm:

1. Initialize current_sum and max_sum with the first element of the array.
2. Traverse through the array from the second element:
   • Update current_sum as max(nums[i], current_sum + nums[i]).
   • Update max_sum as max(max_sum, current_sum).
3. Return max_sum.

Code Implementations in Different Languages:

1. C Language:

#include <stdio.h>

int maxSubArray(int* nums, int numsSize) {
    int current_sum = nums[0], max_sum = nums[0];
    
    for (int i = 1; i < numsSize; i++) {
        current_sum = (nums[i] > current_sum + nums[i]) ? nums[i] : current_sum + nums[i];
        max_sum = (max_sum > current_sum) ? max_sum : current_sum;
    }
    return max_sum;
}

int main() {
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("Maximum Subarray Sum: %d\n", maxSubArray(nums, size));
    return 0;
}

2. C++ Language:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxSubArray(vector<int>& nums) {
    int current_sum = nums[0], max_sum = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        current_sum = max(nums[i], current_sum + nums[i]);
        max_sum = max(max_sum, current_sum);
    }
    
    return max_sum;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "Maximum Subarray Sum: " << maxSubArray(nums) << endl;
    return 0;
}

3. Java:

public class Main {
    public static int maxSubArray(int[] nums) {
        int currentSum = nums[0], maxSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum Subarray Sum: " + maxSubArray(nums));
    }
}

4. Python:

def maxSubArray(nums):
    current_sum = nums[0]
    max_sum = nums[0]
    
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

# Test case
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Subarray Sum:", maxSubArray(nums))

5. C#:

using System;

class Program {
    public static int MaxSubArray(int[] nums) {
        int currentSum = nums[0], maxSum = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            currentSum = Math.Max(nums[i], currentSum + nums[i]);
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return maxSum;
    }

    static void Main() {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        Console.WriteLine("Maximum Subarray Sum: " + MaxSubArray(nums));
    }
}

6. JavaScript:

function maxSubArray(nums) {
    let currentSum = nums[0];
    let maxSum = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}

// Test case
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log("Maximum Subarray Sum:", maxSubArray(nums));

Complexity Analysis:

• Time Complexity: O(n), where n is the number of elements in the array. We only traverse the array once.
• Space Complexity: O(1), since we are only using a constant amount of extra space for current_sum and max_sum.

Conclusion:

This problem is efficiently solvable using Dynamic Programming with a time complexity of O(n) and space complexity of O(1).