Maximum Subarray medium

Problem Statement

Find the contiguous subarray within a one-dimensional array (containing at least one number) which has the largest sum and return its 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

Example 3:

Input: nums = [5,4,-1,7,8] Output: 23

Steps and Explanation

This problem can be efficiently solved using Kadane's Algorithm. The core idea is to maintain a currentMax variable that tracks the maximum sum ending at the current position. We also keep track of a globalMax variable that stores the overall maximum sum encountered so far.

1. Initialization: Set both currentMax and globalMax to the first element of the array.

2. Iteration: Iterate through the array starting from the second element.

3. Update currentMax: For each element, we decide whether to include it in the current subarray. If adding the current element to currentMax results in a larger value, we update currentMax. Otherwise, we start a new subarray from the current element (setting currentMax to the current element).

4. Update globalMax: After updating currentMax, compare it with globalMax. If currentMax is greater, update globalMax.

5. Return globalMax: After iterating through the entire array, globalMax will hold the maximum sum of any contiguous subarray.

Code (C#)

using System;

public class Solution {
    public int MaxSubArray(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0; // Handle empty input
        }

        int currentMax = nums[0];
        int globalMax = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            currentMax = Math.Max(nums[i], currentMax + nums[i]);
            globalMax = Math.Max(globalMax, currentMax);
        }

        return globalMax;
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We use only a few constant extra variables. The algorithm is in-place.