手写代码：最大子数组问题（要求时间复杂度最佳）

public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i : nums) {
            sum = Math.max(i,sum+i); 
            max = Math.max(max,sum);
        }
        return max;
    }

def MaxSubStringSum(numbers):
    tmplist = []
    tmpsum = 0
    if len(numbers) < 1:
        return
    if len(numbers) == 1:
        return numbers[0]
    tmpsum = numbers[0]
    maxnumber = numbers[0]
    flag = True
    if tmpsum <= 0:
        flag = False
    for i in range(1,len(numbers)):
        if numbers[i] > 0:
            nowflag = True
        else:
            nowflag = False
        if nowflag == flag:
            tmpsum += numbers[i]
        else:
            tmplist.append(tmpsum)
            tmpsum = numbers[i]
            flag = nowflag
        maxnumber = max(maxnumber,numbers[i])
    tmplist.append(tmpsum)
    if len(tmplist) == 1 and tmplist[0] <= 0:
        return maxnumber
    tmpsum = 0
    j = 0
    while j < len(tmplist):
        if tmplist[j] <= 0:
            break
        j += 1
    tmpsum = tmplist[j]
    maxsum = tmpsum
    for k in range(j,len(tmplist),2):
        if k+1 < len(tmplist) and (tmplist[k] + tmplist[k+1] > 0):
            tmpsum += (tmplist[k]+tmplist[k+1])
        maxsum = max(maxsum,tmpsum)
        tmpsum = tmplist[k+1]
    return maxsum