from typing import List
import sys
#--------testcase input---------
nums1 = [-2,1,-3,4,-1,2,1,-5,4]
nums2 = [1]
nums3 = [-2,1]
nums4 = [-1,-2]
nums5 = [-1,-2,-3,-4,-5,-6,-7]
nums6 = [-1,-2,-3,1,-5,-6,-7]
#----------------------------main function--------------------------------
# V1.0 暴力解法（LeetCode超时）
#时间复杂度：O(n^3)
#空间复杂度：O(1)
# def maxSubArray(nums: List[int]) -> int:
# if nums:
# maxsum = nums[0]
# for i in range(len(nums)):
# for j in range(i,len(nums)):
# tmpsum = 0
# for k in range(i,j+1):
# tmpsum += nums[k]
# maxsum = max(tmpsum, maxsum)
# return maxsum
# else:
# return 0
# V1.1 暴力解+前缀和（LeetCode超时）
#时间复杂度：O(n^2)
#空间复杂度：O(1)
# def maxSubArray(nums: List[int]) -> int:
# if nums:
# maxsum = -sys.maxsize
# for i in range(len(nums)):
# tmpsum = 0
# for j in range(i,len(nums)):
# tmpsum += nums[j]
# maxsum = max(tmpsum, maxsum)
# return maxsum
# else:
# return 0
# V1.2 优化前缀和
#时间复杂度：O(n)
#空间复杂度：O(1)
# def maxSubArray(nums: List[int]) -> int:
# if nums:
# if len(nums) == 1:
# return nums[0]
# else:
# S = [0]*len(nums)
# S[0] = nums[0]
# minS = 0 #minS要赋0
# maxsum = S[0] #maxsum初值赋S[0]，是为了考虑当最大子序为num[0]时(如[-1,-2])；因为下面的循环直接从S[1]开始考虑，即下面循环出来的最大子序，结束index一定>=1，不会考虑到最大子序为S[0]的情况
# for i in range(1,len(nums)):
# S[i] = S[i-1] + nums[i]
# if minS > S[i-1]:
# minS = S[i-1] #注意minS应是S[0]~S[i-1]中的最小值，而不是S[0]~S[i]
# maxsum = max(maxsum,S[i]-minS)
# return maxsum
# else:
# return 0
# V1.2.1 优化前缀和，比较聪明的写法
#时间复杂度：O(n)
#空间复杂度：O(1)
# def maxSubArray(nums: List[int]) -> int:
# sum = minSum = 0 #minSum要赋0
# maxSum = nums[0] #maxSum初值赋S[0]，是为了考虑当最大子序为num[0]时(如[-1,-2])；因为下面的循环直接从S[1]开始考虑，即下面循环出来的最大子序，结束index一定>=1，不会考虑到最大子序为S[0]的情况
# for i in range(len(nums)):
# sum += nums[i]
# maxSum = max(maxSum,sum-minSum)
# minSum = min(sum,minSum) #注意在用sum-minSum表示nums[0:i]中的最大子序和时，minSum应是nums[0:i-1]中的最小子序和；所以要把minSum=...放在求sum-minSum之后！
# return maxSum
# V1.3 分治法
#时间复杂度：O(nlogn) n是数组长度
#空间复杂度：O(logn) 因为调用栈的深度最多是logn
# def maxSubArray(nums: List[int]) -> int:
# if len(nums) == 1:
# return nums[0]
# elif len(nums) == 2:
# return max(nums[0]+nums[1],max(nums[0],nums[1]))
# midIdx = (len(nums))//2
# Lmax = maxSubArray(nums[:midIdx]) #左闭右开，要用midIdx而不是midIdx-1；LeetCode里要改成self.maxSubArray
# Rmax = maxSubArray(nums[midIdx+1:])
# MLmax = MRmax = MLsum = MRsum = nums[midIdx]
# for i in range(midIdx):
# MLsum += nums[midIdx-i-1]
# MLmax = max(MLsum,MLmax)
# for i in range(len(nums)-midIdx-1):
# MRsum += nums[midIdx+i+1]
# MRmax = max(MRsum,MRmax)
# Mmax = MLmax + MRmax - nums[midIdx]
# return max(Mmax,max(Lmax,Rmax))
# V1.3.1 分治法，写法优化1、2、3
#时间复杂度：O(nlogn) n是数组长度
#空间复杂度：O(logn) 因为调用栈的深度最多是logn
# def maxSubArray(nums: List[int]) -> int:
# if len(nums) == 1:
# return nums[0]
# elif len(nums) == 2:
# return max(nums[0]+nums[1],nums[0],nums[1]) #1
# midIdx = (len(nums))//2
# Lmax = maxSubArray(nums[:midIdx])
# Rmax = maxSubArray(nums[midIdx+1:])
# MLmax = MRmax = MLsum = MRsum = 0 #2 注意这里要把MLmax、MRmax初值赋0而不是-sys.maxsize：比如右边全是负数，赋0则比较完后，MRmax仍为0，即右边一个数都不取；否则，比较完后MRmax会变成[midIdx+1]的负数，结果出错；
# for i in reversed(range(midIdx)): #3 reversed
# MLsum += nums[i]
# MLmax = max(MLsum,MLmax)
# for i in range(midIdx+1,len(nums)):
# MRsum += nums[i]
# MRmax = max(MRsum,MRmax)
# Mmax = MLmax + MRmax + nums[midIdx] #2
# return max(Mmax,Lmax,Rmax) #1
# V1.3.1 动态规划
#时间复杂度：O(n) n是数组长度
#空间复杂度：O(1)
'''
解题思路：
dp[i] 表示到当前位置i(以i为结束index)的最大子序列和
状态转移方程为：dp[i] = max(dp[i-1] + nums[i], nums[i])
'''
def maxSubArray(nums: List[int]) -> int:
currIdxEndMaxSum = maxSum = nums[0]
for i in range(1,len(nums)):
currIdxEndMaxSum = max(currIdxEndMaxSum + nums[i], nums[i])
maxSum = max(currIdxEndMaxSum, maxSum)
return(maxSum)
#--------testcase output---------
print(maxSubArray(nums1))
print(maxSubArray(nums2))
print(maxSubArray(nums3))
print(maxSubArray(nums4))
print(maxSubArray(nums5))
print(maxSubArray(nums6))
