Maximum-Subarray - DSA Question 3

Sure, let's break down the "Maximum Subarray" problem in detail and provide a simple explanation along with Java code.

Problem Statement:

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

Approach and Explanation:

Kadane's Algorithm:

Kadane's algorithm is an efficient way to find the maximum subarray sum. It works by iterating through the array and keeping track of the maximum subarray ending at the current position. If the sum becomes negative, it means the current subarray is not contributing positively, so it's better to start over from the current position.

Step-by-Step Explanation:

1. Initialize Variables:

   • Initialize two variables, maxSum and currentSum, to track the overall maximum sum and the current subarray sum.

   • Set maxSum and currentSum to the first element of the array (nums[0]).

2. Iterate Through the Array:

   • Start iterating from the second element (index 1) to the end of the array.

   • For each element, update currentSum:

     • If currentSum becomes negative, reset it to the current element. This step ensures that we are always considering a positive subarray.

     • If currentSum is positive, add the current element to it, extending the subarray.

3. Update maxSum:

   • Update maxSum with the maximum value between the current maxSum and currentSum. This step ensures that we are always storing the maximum subarray sum encountered so far.

4. Continue Iterating:

   • Continue the iteration until the end of the array.

5. Return maxSum:

   • After the iteration is complete, return maxSum as the result.

Java Code:

public class MaximumSubarray {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0]; // Initialize maxSum with the first element
        int currentSum = nums[0]; // Initialize currentSum with the first element

        // Iterate through the array starting from the second element
        for (int i = 1; i < nums.length; i++) {
            // If currentSum becomes negative, start a new subarray from the current element
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            // Update maxSum with the maximum value between currentSum and maxSum
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum; // Return the maximum subarray sum
    }
}

Explanation of the Code:

• The maxSubArray function takes an integer array nums as input.

• It initializes maxSum and currentSum with the first element of the array (nums[0]).

• It iterates through the array, updating currentSum based on the conditions explained above.

• The maxSum variable keeps track of the maximum subarray sum encountered so far.

• After the iteration, it returns maxSum as the result, which represents the maximum subarray sum in the given array.

This approach ensures an efficient solution to find the maximum subarray sum and is widely used in competitive programming and real-world applications where optimizing time complexity is essential.