连续子数组的最大和

F（i）：以arr[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变
F（i）=max(F（i-1）+arr[i] , arr[i])

arr = [1, -2, 3, 10, -4, 7, 2, -5]

# 暴力求解
maxsum = 0
for i in range(len(arr)):
    cursum = 0
    for j in range(i, len(arr)):
        cursum += arr[j]
        if cursum > maxsum:
            maxsum = cursum
print(maxsum)

# 动态规划 1
cursum, maxsum = 0, 0
for i in range(len(arr)):
    if arr[i] > arr[i] + cursum:  # 此时cursum<0
        cursum = arr[i]
    else:
        cursum = arr[i] + cursum
    if cursum > maxsum:
        maxsum = cursum
print(maxsum)

# 动态规划 2
cursum, maxsum = 0, 0
for i in range(len(arr)):
    cursum += arr[i]
    if cursum > maxsum:
        maxsum = cursum
    if cursum < 0:
        cursum = 0
print(maxsum)


# 动态规划 3
cursum, maxsum = 0, 0
for i in range(len(arr)):
    cursum = max(arr[i], arr[i] + cursum)
    maxsum = max(maxsum, cursum)
print(maxsum)