|
关于最大子列和的问题一直是各种语言最经典的问题之一，今天用Python来简单解决一下。
先看一下问题 ：
给定K个整数组成的序列{ N1, N2, ..., NK}，“连续子列”被定义为{ Ni,
Ni+1, ..., Nj}，其中 1 <= i <= j <= K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
输入格式：
输入第1行给出正整数 K (<= 100000)；第2行给出K个整数，其间以空格分隔。
输出格式：
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。
输入样例：
6 -2 11 -4 13 -5 -2
输出样例：
20
以下是完整的解决代码：
# coding:utf-8
# 输入列表
def kInput():
k = int(input('请输入您要输入的数字个数'))
if 0 < k <= 100000:
input_number = str(raw_input('请按照数字+空格的格式输入%s个整数（例如3 4 5）' % k))
split_number = input_number.split(' ')
return split_number
else:
print '请输入恰当的数字（1 到 100000）'
# 求取最大子列和
def sum_lis(list1):
sum_list = 0
for i in range(len(list1)):
if int(list1[i]) < 0:
sum_list = 0
else:
sum1 = 0
for j in list1[i:]:
sum1= sum1 + int(j)
if sum1 > sum_list:
sum_list = sum1
return sum_list
k_list = kInput()
k_sum = sum_lis(k_list)
print k_sum
当然，这个代码只是简单地解决了问题的主要部分，其他问题，例如：
1.验证输入的是否都是整数（isinstance(x,int)是否为真）；
2.验证输入的整数个数是否和开始输入的数字K一致，这些都是需要验证的(len(split_number和k的大小比较))
感兴趣的童鞋可以加上试一试。
如果有其他问题，请留言。
| 
转播
