LargestSubarraySum

Largest SubArray Sum

https://app.laicode.io/app/problem/489

Description

Given an unsorted integer array, find the subarray that has the greatest sum. Return the sum and the indices of the left and right boundaries of the subarray. If there are multiple solutions, return the leftmost subarray.

Assumptions

• The given array is not null and has length of at least 1.

Examples

• {2, -1, 4, -2, 1}, the largest subarray sum is 2 + (-1) + 4 = 5. The indices of the left and right boundaries are 0 and 2, respectively.

• {-2, -1, -3}, the largest subarray sum is -1. The indices of the left and right boundaries are both 1

  Return the result in a array as [sum, left, right]

Medium

Dynamic Programming

Assumption

The input array cannot be null or empty

Algorithm

This is another alternative questions of the classic Largest Subarray Sum problem.

We use linear scan and look back, too. This time, however, we need some additional variables to record the current start index, the start and end index that gives us the subarray with the maximum sum.

Solution

Code

public class Solution {
  public int[] largestSum(int[] array) {
    // Write your solution here
    if (array == null || array.length == 0) {
      return new int[] {};
    }
    int currentSum = array[0];
    int maxSum = array[0];
    int currentStart = 0;
    int maxStart = 0;
    int maxEnd = 0;
    for (int currentEnd = 1; currentEnd < array.length; currentEnd++) {
      if (currentSum < 0) {
        currentSum = array[currentEnd];
        currentStart = currentEnd;
      } else {
        currentSum += array[currentEnd];
      }
      if (currentSum > maxSum) {
        maxSum = currentSum;
        maxStart = currentStart;
        maxEnd = currentEnd;
      }
    }
    return new int[] {maxSum, maxStart, maxEnd};
  }
}

Complexity

Time

Linear scan & look back for one iteration ⇒ O(n)

Space:

Constant space ⇒ O(1)