maxSubArray

Python

class Solution:
    # @param A : tuple of integers
    # @return an integer
    def maxSubArray(self, A):
        if not A:
          return 0

        max_sum = A[0]
        current_sum = A[0]

        for i in range(1, len(A)):
          current_sum = max(A[i], current_sum + A[i])
          max_sum = max(max_sum, current_sum)

        return max_sum  

JavaScript

/**
 * @param {number[]} arr
 * @returns {number}
 */
export default function maxSubArray(arr) {
  if (!arr || arr.length === 0) {
    return 0;
  }

  let maxSum = arr[0];
  let currentSum = arr[0];

  for (let i = 1; i < arr.length; i += 1) {
    currentSum = Math.max(arr[i], currentSum + arr[i]);
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}