Maximum Subarray - Java Solution

1. Introduction

This blog post discusses the "Maximum Subarray" problem, a fundamental problem in the field of computer science, specifically in the realm of dynamic programming and divide-and-conquer strategies. The problem focuses on finding a contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Problem

Given an integer array nums, the goal is to find the subarray that yields the largest sum and return this sum.

Examples:

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

Output: 6

- Input: nums = [1]

Output: 1

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

Output: 23

2. Solution Steps

1. Initialize two variables, maxSoFar and maxEndingHere, with the first element of the array.

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

- Update maxEndingHere by adding the current element.

- If maxEndingHere is less than the current element, reset it to the current element value.

- Update maxSoFar to be the maximum of maxSoFar and maxEndingHere.

3. Return maxSoFar as the result.

3. Code Program

public class MaximumSubarray {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums)); // Test the function
    }

    // Function to find the largest sum of any contiguous subarray
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int maxSoFar = nums[0], maxEndingHere = nums[0];

        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }
}

Output:

6

Explanation:

1. maxSubArray: This function calculates the largest sum of a contiguous subarray in nums.

2. It uses the Kadane’s Algorithm, which is an efficient way to solve this problem in O(n) time complexity.

3. maxEndingHere keeps track of the maximum sum of subarrays ending at the current index.

4. maxSoFar stores the maximum sum encountered so far.

5. In each iteration, maxEndingHere is updated to include the current element or to start a new subarray from the current element if it offers a higher sum.

6. maxSoFar is updated to ensure it always holds the highest sum found.

7. This approach efficiently finds the maximum subarray sum without the need for nested loops, ensuring optimal performance.