# 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 {
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;
// Maximum sum of current subarray
int currentMax = nums;

// 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
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
}
}

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);
}
}
``````