Maximum Subarray medium

Problem Statement

Find the contiguous subarray within a one-dimensional array (containing at least one number) which has the largest sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1] Output: 1 Explanation: The only subarray is [1], thus the maximum sum is 1.

Steps and Explanation

The problem can be solved efficiently using Kadane's Algorithm. The core idea is to maintain a variable max_so_far that tracks the maximum sum encountered so far and a variable max_ending_here that tracks the maximum sum ending at the current position.

1. Initialization: max_so_far and max_ending_here are initialized to the first element of the array.

2. Iteration: The algorithm iterates through the array. For each element:

   • max_ending_here is updated. If adding the current element to max_ending_here results in a larger sum, we keep the sum; otherwise, we restart max_ending_here with the current element (because a negative sum would decrease the overall sum).
   • max_so_far is updated to the maximum of max_so_far and max_ending_here. This ensures we keep track of the largest sum seen so far.

3. Return Value: After iterating through the entire array, max_so_far holds the maximum contiguous subarray sum.

Code (C++)

#include <iostream>
#include <vector>
#include <climits> // For INT_MIN

using namespace std;

int maxSubArray(vector<int>& nums) {
    int max_so_far = nums[0];
    int max_ending_here = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        max_ending_here = max(nums[i], max_ending_here + nums[i]);
        max_so_far = max(max_so_far, max_ending_here);
    }
    return max_so_far;
}

int main() {
    vector<int> nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    vector<int> nums2 = {1};
    vector<int> nums3 = {-1}; //test case for all negative numbers

    cout << "Maximum contiguous sum for nums1: " << maxSubArray(nums1) << endl; // Output: 6
    cout << "Maximum contiguous sum for nums2: " << maxSubArray(nums2) << endl; // Output: 1
    cout << "Maximum contiguous sum for nums3: " << maxSubArray(nums3) << endl; // Output: -1

    return 0;
}

Complexity

• Time Complexity: O(n), where n is the size of the input array. The algorithm iterates through the array once.
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space to store the variables max_so_far and max_ending_here.