#!/usr/bin/python
# ==============================================================================
# Author:   Tao Li (taoli@ucsd.edu)
# Date:     May 5, 2015
# Question: 053-Maximum-Subarray
# Link:     https://leetcode.com/problems/maximum-subarray/
# ==============================================================================
# Find the contiguous subarray within an array (containing at least one number) 
# which has the largest sum.
# 
# For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
# the contiguous subarray [4,-1,2,1] has the largest sum = 6.
# 
# click to show more practice.
# 
# More practice:
# If you have figured out the O(n) solution, try coding another solution using 
# the divide and conquer approach, which is more subtle.
# ==============================================================================
# Method: Simple DP implementation
# Time Complexity: O(n)
# Space Complexity: O(1)
# Note: Try the divide and conquer approach next time
# ==============================================================================

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def maxSubArray(self, nums):
        maxVal = -float('inf')
        total = 0
        for i in nums:
            total += i
            if total > maxVal:
                maxVal = total
            if total < 0:
                total = 0
        return maxVal

if __name__ == '__main__':
    print Solution().maxSubArray([-1])