Maximum Subarray Sum

Objective

Given an array of integers, find the maximal sum of any subarray (contiguous block of integers) of the array.

Observations

  1. We want to find the largest sum of any contiguous sequence of integers in the array.
  2. When calculating the running sum of a contiguous block of numbers, we don’t want to include a previously-calculated contiguous block that sums to a value that is less than the value stored at the current index. For example, if we have nums = [1, -4, 1, 2], the sum of nums0 + nums1 = 1 + -4 = -3 is less than the value of nums2 = 1, so we would not include a block consisting of indices 0 through 1 in our maximal contiguous block.
  3. A subarray can sum to a maximal value but still contain negative values in its middle elements. For example, if we have nums = [2, -1, 1, 2], our maximal sum comes from a subarray containing all elements of the array (2 + -1 + 1 + 2 = 4), which includes the negative value nums1 = -1.
Code
class Solution {
	// Kadane's Algorithm
	public int maximumSubarraySum(int[] nums) {
		/* Case: Empty array */
		if (nums.length == 0) {
			return 0;
		}
		
		/* Case: One or more elements */
		// Maximum sum of any subarray
		int totalMax = nums[0];
		// Maximum sum of current subarray
		int currentMax = nums[0];
		
		// This only runs if the array contains more than one element
		// Note that this starts at index 1, because 'totalMax' and 'currentMax' were initialized to nums[0]
		for (int i = 1; i < nums.length; i++) {
            // Update running maximum for current subarray
			currentMax = Math.max(
                // If this is larger, new value simulates possible beginning of new subarray
                nums[i], 
                // If this is larger, new value simulates continuing to sum existing subarray
                currentMax + nums[i]
            );
            
            // Update maximum value of any subarray
			totalMax = Math.max(currentMax, totalMax);
		}
		
        // Maximum subarray sum
		return totalMax;
	}
}

public class MaximumSubarraySum {
	
	public static void main(String[] args) {
		Solution s = new Solution();
		int[] nums = {-1, 5, 7, -20, 8, 4, -1, 2, -2};
		int result = s.maximumSubarraySum(nums);
		System.out.println(result);
	}
}
Spread the love...

Leave a Reply