# python编写PAT甲级 1007 Maximum Subsequence Sum

wenzongxiao1996 2019.4.3

## 题目

Given a sequence of K integers { N​1, N2, ..., N​K}. A continuous subsequence is defined to be { N​i, N​i+1, ..., N​j} where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification: Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification: For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input: 10 -10 1 2 3 4 -5 -23 3 7 -21 Sample Output: 10 1 4

## 暴力解法(超时了)

```def seq_sum(s):
"""求序列的所有元素之和"""
result = 0
for i in range(len(s)):
result += s[i]
return result

def main():
n = int(input())
seq = [int(i) for i in input().split()]
max = -1
pos_i = 0
pos_j = n-1
for i in range(n):
for j in range(i,n):
sum_temp = seq_sum(seq[i:j+1])
if sum_temp > max:
max = sum_temp
pos_i = i
pos_j = j
if max < 0:
print(0,seq[pos_i],seq[pos_j])
else:
print(max,seq[pos_i],seq[pos_j])

if __name__ == '__main__':
main()```

## 分治法

```def division_solution(seq,left,right):
if left == right: # 递归出口
if seq[left] >= 0:
return left,right,seq[left]
else:
return left,right,-1
center = (left+right)//2 # 地板除

# 从中间到左边的最大子串
sum_left = 0
max_sum_left = -1  # 一定要设为负数
pos_left = left   # 要返回下标
for i in range(left,center+1)[::-1]:  # 反向迭代
sum_left += seq[i]
if sum_left >= max_sum_left:
max_sum_left = sum_left
pos_left = i

# 从中间到右边的最大子串
sum_right = 0
max_sum_right = -1  # 一定要设为负数
pos_right = right  # 要返回下标
for i in range(center+1,right+1):
sum_right += seq[i]
if sum_right > max_sum_right:
max_sum_right = sum_right
pos_right = i

# 递归求解左右两个子问题
i_left,j_left,max_left_sum = division_solution(seq,left,center)
i_right,j_right,max_right_sum = division_solution(seq,center+1,right)

if max(max_left_sum,max_right_sum,max_sum_left+max_sum_right) < 0:
return left,right,-1
else:
if max(max_left_sum,max_right_sum,max_sum_left+max_sum_right) == max_left_sum:
return i_left,j_left,max_left_sum
elif max(max_left_sum,max_right_sum,max_sum_left+max_sum_right) == max_right_sum:
return i_right,j_right,max_right_sum
else:
return pos_left,pos_right,max_sum_left+max_sum_right

def main():
n = int(input())
seq = [eval(i) for i in input().split()]
i,j,sum_max = division_solution(seq,0,n-1)
if sum_max < 0:
print(0,seq[0],seq[-1])
else:
print(sum_max,seq[i],seq[j])

if __name__ == '__main__':
main()```

## 动态规划

```def main():
n = int(input())
seq = [eval(i) for i in input().split()]
sum_max = -1
pos_i = 0
pos_i_temp = 0 # 最大子序列的左下标不能随意更改，只有找到了更大的子串才能改，用这个变量先保存着当前寻找的子串的左下标
pos_j = n-1
sum_temp = 0
for i in range(n):
sum_temp += seq[i]
if sum_temp > sum_max:
sum_max = sum_temp
pos_j = i
pos_i = pos_i_temp
elif sum_temp < 0:# 和小于0的子串不需要考虑
sum_temp = 0
pos_i_temp = i+1
if sum_max < 0:
print(0,seq[0],seq[-1])
else:
print(sum_max,seq[pos_i],seq[pos_j])

if __name__ == '__main__':
main()```

0 条评论

• ### android 调用 python

我这里使用AS，如果使用ec开发的直接看 http://www.srplab.com/cn/index.html 官方下载的开发包 里面有demo，我下载...

• ### 用算号器来破解SAPR/3

如何用算号器激活SAP系统。 新建用户，必须使用具有SAP_ALL权限的用户，如以我的用户为SAP为例； 用SAP_ALL权限的用户(如SAP)登录，运行事务 ...

• ### 深度学习算法原理——神经网络的基本原理

对于上述的神经元，其输入为x1x1x_1，x2x2x_2，x3x3x_3以及截距+1+1+1，其输出为：

• ### 单细胞转录组数据的个性化分析汇总

既然是个性化分析，理论上就是无穷无尽的，而且我在 有一种生意双方都觉得亏 提到过，专业的工程师觉得为客户学习一个R包收费2000合情合理，但是委托者觉得一个项目...

• ### 癌症中克隆种群结构统计推断分析软件PyClone安装小记

PyClone 是一种用于推断癌症中克隆种群结构的统计模型。 它是一种贝叶斯聚类方法，用于将深度测序的体细胞突变集分组到假定的克隆簇中，同时估计其细胞流行率（p...

• ### Appium系列|Appium测试框架搭建(二)

上一个小节已经创建了三个Page类，每个应用里会有很多个Page类，Page类多的话要获取到需要的Page类就比较麻烦，这时候可以新建一个用来管理各个page类...

• ### 据结构与算法(八) 二叉树的练习

•设定levelSize初始值为1（只有一个根节点）•当进行while循环的时候 levelsize-- 操作。因为levelSize和每层节点个数相等。所以当...