Given an unsorted integer array, find the subarray that has the greatest sum. Return the sum.

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
• {-2, -1, -3}, the largest subarray sum is -1

Approach: DP. Base Case : m[0] = input[0]

Deduction rule: m[] represents the sum of the subarray from 0 to i element including ith element.

m[i] = m[i - 1] + input[i] if m[i - 1] > 0

otherwise, m[i] = input[i];

public class Solution {
  public int largestSum(int[] array) {
    // Write your solution here.
    int[] m = new int[array.length];
    m[0] = array[0];
    int result = m[0];

    for (int i = 1; i < array.length; i++) {
      if (m[i - 1] > 0) {
        m[i] = m[i - 1] + array[i];
      } else {
        m[i] = array[i];
      }
      result = Math.max(result, m[i]);
    }
    return result;
  }
}

time: O(n) Space: O(n)

optimize the space to O (1)

public class Solution {
  public int largestSum(int[] array) {
    // Write your solution here.
    int cur = array[0];
    int result = cur;

    for (int i = 1; i < array.length; i++) {
      cur = Math.max(array[i], array[i] + cur);
      result = Math.max(result, cur);
    }
    return result;
  }
}

Return the index of largest sub array sum:

Use the start pointer to record the cur start,. two cases : cur > 0; cur < 0.

when cur > result we need update the result and the sol_start and so_l_end index.

public class Solution {
  public int largestSum(int[] array) {
    // Write your solution here.
    int cur = array[0];
    int result = cur;
    int start = 0;
    int sol_start = 0;
    in sol_end = 0;

    for (int i = 1; i < array.length; i++) {
      if (cur > 0) {
        cur = array[i] + cur;
      } else {
        cur = array[i];
        start = i;
      }
      if (cur > result) {
        result = cur;
        sol_start = start;
        sol_end = i;
      }
    }
    return result;
  }
}