题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个,或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。
不考虑纯负数的数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import optparse
def FindMaximumSumOfSubArray(lstda): # 找到最大的子数组的和
# print(lstda)
sum, max = 0, 0
accum_sub, max_sub = [], []
for i in range(len(lstda)):
if sum < 0: # 如果前部加起来为 负数,则重新开始计算,
sum = 0
accum_sub = [] # 这里是 负数的话重新统计 子数集
sum = sum + lstda[i]
# print(accum_sub)
accum_sub.append(lstda[i]) # 添加进去 acc 列表里面
# print(accum_sub)
else:
sum = sum + lstda[i]
accum_sub.append(lstda[i])
if sum >= max : # 每次 循环都进行判断,如果 sum 和 大于了 max,则 max 进行重新赋值,在进行循环计数进行判断;如果小于,则进行再次进行上部分循环 0
max = sum
max_sub = []
# max_sub = accum_sub
for d in accum_sub:
max_sub.append(d) # 一定要这种写法,否则负数会跟在后面
# 1,2,3,4,5,-1 -1 会输出,做个判断
print(max_sub)
print(max)
"""
上面的大致思路:每一次循环进行相加,都会进行 【if sum > max : 】这一步比较,这里始终会是最大值,子集一样。题目有一个坑点是要连续的子集。小于负数了,从 下一位 重新开始
即使全是 负数,总有一个数是最大的
"""
def validation(data): # 验证输入的数据是否正确,符合要求
t_a = data.replace('-','') # isdigit 无法判断 负数,将 - 符号替换为空
try:
if t_a[1] != ',' or len(t_a) == 1: # 是否有逗号,但是过滤不完全,后面一段代码直接+try
return False
except:
print("Wrong data format!")
return False
try:
for i in t_a.split(','):
# print(type(i))
if i.isdigit() == False: # 判断是否是数字
print("The data is not numeric!")
return False
one_list = list(map(int, data.split(',')))
FindMaximumSumOfSubArray(one_list)
except:
print("Wrong data format!")
return False
return True
def main():
parser = optparse.OptionParser("usage: %prog [options] args", version="%prog 6.0 ")
parser.add_option('-i', '--input', dest='Array_data', type='string',help='For example, you can enter data: 1,2,3,4,5。The number of bits of data must be greater than 2.')
(options, args) = parser.parse_args()
mathdata = options.Array_data
if mathdata == None:
print(parser.usage)
exit(0)
if validation(mathdata) == False: # 验证数据
exit("The data you entered is incorrect, please use the help command.")
if __name__ == "__main__":
main()