PTA：01-复杂度2 Maximum Subsequence

思路

1.这个算法是最大子列和的一个改版，需要我们定位最大子列和的第一个和最后一个数。所以相应的我们仍然可以使用在线处理算法。
2.有几个特殊测试需要注意：全为负数，只有负数和零，只有一个正数。我们需要在输出时做相应的处理。
3.这里说个“坑”，关于测试点3：并列和对应相同i但是不同j，即尾是0。有多个并列和时，tem+=K_list[i]可能最开始比max小，这时候可能定位不到最开始的第一个数，即最后i的输出结果不正确。所以我增加了一个辅助变量，记录重新累加的第一个数。
测试用例：
10
1 2 0 -5 1 0 0 2 3 0
正确输出：6 1 3
如果测试点3错误，可能会输出：6 3 3

PYTHON

K = int(input())
K_list = input().split()

for i in range(0, K):
    K_list[i] = int(K_list[i])

tem = 0
max_sum = 0
f_ind = -1
fi_ind = -1
l_ind = -1

f_flag = True
fi_flag = True
l_flag = True
p_flag = False
z_flag = False
for i in range(0, K):
    if K_list[i] > 0:
        p_flag = True
    elif K_list[i] == 0:
        z_flag = True

    tem += K_list[i]
    if tem > max_sum:
        max_sum = tem
        if f_flag:
            if fi_flag:
                f_ind = K_list[i]
            else:
                f_ind = fi_ind
            f_flag = False
        l_ind = K_list[i]
    elif tem == 0 and K_list[i] ==0:
        if f_flag:
            f_ind = K_list[i]
            f_flag = False
    elif tem > 0 and f_flag:
        if f_flag and fi_flag:
            fi_ind = K_list[i]
            fi_flag = False

    elif tem < 0:
        tem = 0
        f_flag = True
        fi_flag = True


if not p_flag and z_flag:
    f_ind = 0
    l_ind = 0
if p_flag:
    print("%d %d %d"%(max_sum, f_ind, l_ind))
else:
    if z_flag:
        print("%d %d %d"%(max_sum, f_ind, l_ind))
    else:
        print("%d %d %d"%(max_sum, K_list[0], K_list[K-1]))