连续最大和

题目描述

一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3

输入描述:

输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。

输出描述:

所有连续子数组中和最大的值。

示例1

输入    3     -1 2 1

输出     3

结题思路：

递归地定义最优解
最优解必定是序列最后一个元素和前n-1个元素最优组合

f(n-1):在n-1位置可以取得的最大和值；（）

 

 

代码：

n=int(input())
arr=[int(x) for x in input().split()]

l=len(arr)
data=[0 for i in range(l)]
index_data=[0 for i in range(l)]
max_index=0
for i in range(l):
    if i==0:
        data[i]=arr[i]
    else:
        d1=arr[i]+data[i-1]
        d2=arr[i]
        if d1>=d2:
            data[i]=d1
            index_data[i]=1
        else:
            data[i]=d2
# 获取连续最大和的索引
max_index=index_data.index(max(index_data))
result=[]
while max_index>=0 and index_data[max_index]:
    result.append(max_index)
    max_index-=1
result.append(max_index)

print(max(data))
print(data,"\n", index_data,sorted(result))