Maximum Subarray

• Initialize a variable maxSum to the smallest possible integer value.
• Use a nested loop structure. The outer loop, with index i, iterates from the start to the end of the array, fixing the starting element of a subarray.
• The inner loop, with index j, iterates from i to the end of the array, fixing the ending element of a subarray.
• For each subarray defined by i and j, calculate its sum. A third loop can be used, or more efficiently, a currentSum variable can be updated within the second loop.
• Compare the currentSum of each subarray with maxSum. If currentSum is greater, update maxSum.
• After iterating through all possible subarrays, maxSum will hold the maximum subarray sum.

This method considers every possible subarray. We can define a subarray by its start and end indices. We use two nested loops to iterate through all possible start and end points. The outer loop selects the starting index i, and the inner loop selects the ending index j.

For each pair of (i, j), we calculate the sum of the elements in nums from index i to j. We maintain a global variable, maxSum, initialized to a very small number (like Integer.MIN_VALUE). As we calculate the sum of each subarray, we compare it with maxSum and update maxSum if the current subarray's sum is larger.

An optimization to the naive three-loop approach is to calculate the sum iteratively in the second loop. As j increments, we just add nums[j] to the sum of the subarray nums[i...j-1]. This reduces the complexity from O(n³) to O(n²).

1class Solution {2    public int maxSubArray(int[] nums) {3        int n = nums.length;4        int maxSum = Integer.MIN_VALUE;5 6        for (int i = 0; i < n; i++) {7            int currentSum = 0;8            for (int j = i; j < n; j++) {9                // Add the current element to the subarray sum10                currentSum += nums[j];11                // Update maxSum if the current subarray sum is greater12                if (currentSum > maxSum) {13                    maxSum = currentSum;14                }15            }16        }17        return maxSum;18    }19}

• Define a recursive function that takes the array and the left and right indices as input.
• Base Case: If left equals right, there is only one element, so return that element's value.
• Divide: Find the middle index mid of the current segment.
• Conquer:
  1. Recursively find the maximum subarray sum for the left half (left to mid).
  2. Recursively find the maximum subarray sum for the right half (mid + 1 to right).
  3. Find the maximum subarray sum that crosses the midpoint. This involves finding the maximum sum of a subarray starting at mid and extending to the left, and the maximum sum of a subarray starting at mid + 1 and extending to the right. The sum of these two is the crossing sum.
• Combine: Return the maximum of the three sums calculated in the conquer step.

The divide and conquer strategy involves splitting the array into two halves and solving the problem recursively for each half. The crucial part is the 'combine' step, where we consider the case that the maximum subarray spans across the midpoint.

Let's define a function findMax(nums, left, right):

1. If left == right, we have a single-element array, so we return nums[left].
2. Otherwise, we find the midpoint mid = (left + right) / 2.
3. The result is the maximum of: a. findMax(nums, left, mid): The max subarray sum in the left half. b. findMax(nums, mid + 1, right): The max subarray sum in the right half. c. findCrossingSum(nums, left, mid, right): The max subarray sum that crosses the midpoint.

To find the crossing sum, we iterate from mid down to left to find the largest possible sum for the left part of the crossing subarray. Then, we iterate from mid + 1 up to right to find the largest sum for the right part. The sum of these two parts gives the maximum crossing subarray sum.

1class Solution {2    public int maxSubArray(int[] nums) {3        return findMaxSubArray(nums, 0, nums.length - 1);4    }5 6    private int findMaxSubArray(int[] nums, int left, int right) {7        // Base case: only one element8        if (left == right) {9            return nums[left];10        }11 12        int mid = left + (right - left) / 2;13 14        // 1. Max subarray sum in left half15        int leftSum = findMaxSubArray(nums, left, mid);16        // 2. Max subarray sum in right half17        int rightSum = findMaxSubArray(nums, mid + 1, right);18        // 3. Max subarray sum crossing the midpoint19        int crossSum = findMaxCrossingSubArray(nums, left, mid, right);20 21        // Return the maximum of the three22        return Math.max(Math.max(leftSum, rightSum), crossSum);23    }24 25    private int findMaxCrossingSubArray(int[] nums, int left, int mid, int right) {26        int leftSum = Integer.MIN_VALUE;27        int currentSum = 0;28        for (int i = mid; i >= left; i--) {29            currentSum += nums[i];30            if (currentSum > leftSum) {31                leftSum = currentSum;32            }33        }34 35        int rightSum = Integer.MIN_VALUE;36        currentSum = 0;37        for (int i = mid + 1; i <= right; i++) {38            currentSum += nums[i];39            if (currentSum > rightSum) {40                rightSum = currentSum;41            }42        }43 44        return leftSum + rightSum;45    }46}

• Initialize two integer variables: globalMax and currentMax, both to the value of the first element in the array.
• Iterate through the array starting from the second element (i = 1).
• In each iteration, update currentMax. The new currentMax is the maximum of the current element nums[i] or the sum of currentMax and nums[i]. This step decides whether to extend the existing subarray or start a new one.
• After updating currentMax, compare it with globalMax and update globalMax if currentMax is larger.
• After the loop finishes, globalMax will contain the largest subarray sum.

This algorithm iterates through the array just once. It maintains a variable currentMax which, at each position i, stores the maximum possible sum of a subarray that ends at i. This subarray is either just the element nums[i] itself or the element nums[i] appended to the maximum subarray ending at the previous position i-1.

Thus, the recurrence relation is: currentMax(i) = max(nums[i], currentMax(i-1) + nums[i])

We also need another variable, globalMax, to store the maximum sum found over all positions. At each step, after calculating currentMax(i), we update globalMax with max(globalMax, currentMax(i)). This ensures we keep track of the overall maximum, as the maximum subarray might not end at the last element of the array.

1class Solution {2    public int maxSubArray(int[] nums) {3        if (nums == null || nums.length == 0) {4            // As per constraints, nums.length >= 1, but good practice.5            return 0; 6        }7 8        int globalMax = nums[0];9        int currentMax = nums[0];10 11        for (int i = 1; i < nums.length; i++) {12            // Decide whether to extend the previous subarray or start a new one.13            currentMax = Math.max(nums[i], currentMax + nums[i]);14            15            // Update the overall maximum sum found so far.16            if (currentMax > globalMax) {17                globalMax = currentMax;18            }19        }20 21        return globalMax;22    }23}