Title:

Maximum Subarray

Specification:

Given an integer array `nums`,
find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Examples:

Example 1:

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Initial Code and Signature:

``` public interface MaxSumSubArrayFinder { public int maxSubArray(int[] nums); } ```

Algorithm:

1. Start from the beginning of the array.
2. Add the elements to the maximum sub-array one by one.
3. Compare the sum of the elements with the maximum sum.
4. Update the maximum sum if required.
5. As soon as the sum of the elements gets negative,
reset sum to zero.
6. Continue (Go to 2-).

Run-Time Analysis:

GitHub Project:

Code:

``` /** * * @author Mahsa Sadi * * @since 2020 - 04 - 08 * * License: Creative Commons * * Copyright by Mahsa Sadi * */ public class MaxSumSubArrayFinderV1 implements MaxSumSubArrayFinder { /** * Problem : Maximum Sub-Array * * * * * Description: * Given an integer array nums, * find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. * * * Solution: * * 1- Start from the beginning of the array. * * 2- Add the elements to the maximum sub-array one by one. * * 3- Compare the sum of the elements with the maximum sum. * * 4- Update the maximum sum if required. * * 5- As soon as the sum of the elements gets negative, * reset sum to zero. * * 6- Continue (Go to 2-). * * */ int maxSum, sum; boolean maxSumSet = false; @Override public int maxSubArray(int[] nums) { maxSum = sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums [i]; if (sum > maxSum || ! maxSumSet) { maxSum = sum; maxSumSet = true; } if (sum < 0) sum = 0; } return maxSum; } } ```