Objective
Given an array of integers, find the maximal sum of any subarray (contiguous block of integers) of the array.
Observations
- We want to find the largest sum of any contiguous sequence of integers in the array.
- 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 ofnums0 + nums1 = 1 + -4 = -3is less than the value ofnums2 = 1, so we would not include a block consisting of indices0through1in our maximal contiguous block. - 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 valuenums1 = -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);
}
}