Python:最大子数组和
Python: Maximum Subarray Sum
今天刚开始学习Python,对它的功能不是很了解。然而,我发现了最大子数组问题,并想尝试用我掌握的几个简单的逻辑命令来解决它。我被卡住了,几乎可以肯定问题出在我的逻辑上而不是语法上,尽管我很可能是错的。到目前为止,这是我的代码...
def maxSequence(arr): #Latest attempt, some issue.
old_arr = []
print(arr)
while old_arr != arr:
old_arr = arr
if arr[0] > 0 and arr[len(arr)-1] > 0: #For when both sides are positive, need to be sure there is not anything to be gained by eliminating some side section
new_sum = 0
y=0
while new_sum >= 0 and y != -1:
new_sum = sum(arr[:y])
y=y+1
if y == len(arr)-1:
y=-1
if y != -1:
arr = arr[y-1:]
print("left %s" %(new_sum))
print("left %s" % (arr))
new_sum = 0
y = 0
while new_sum >= 0 and y != -1:
new_sum=sum(arr[(len(arr)-y):])
y=y+1
if y == len(arr)-1:
y=-1
if y != -1:
arr = arr[:len(arr)-y+1]
print("right %s" %(new_sum))
print("right %s" % (arr))
else:
while arr[0] < 0 or arr[len(arr)-1] < 0: #To eliminate negatives on sides
if arr[0] < 0:
arr = arr[1:]
if arr[len(arr)-1] < 0:
arr = arr[:len(arr)-1]
print("negative %s" % (arr))
print(arr)
print(sum(arr))
各种打印函数显示程序做出的每个决定,并帮助我可视化执行循环时发生的事情。
给出列表时没有给出正确的结果 105
[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26]
最终总和为 94,已将列表缩减为
[21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
很抱歉 post,但我就是想不通我做错了什么。预先感谢您的帮助!
这是将上述列表作为输入时的输出,我已经检查并查看了每一步,列表中的每一项删除对我来说都是合乎逻辑的,我不知道怎么会得到一个结束总和为105。如果有人能帮助我理解,我将不胜感激!
[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25,
-27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10,
-25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26]
negative [26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25,
-8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28,
11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17]
left -22
left [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15,
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17]
right -8
right [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15,
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25, -22, 8, 9, -4]
negative [3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15,
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25, -22, 8, 9]
left -3
left [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11,
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6,
-13, -13, 25, -22, 8, 9]
right -5
right [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11,
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6,
-13, -13, 25]
negative [15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11,
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6,
-13, -13, 25]
left -5
left [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25]
right -1
right [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6]
negative [1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18,
6]
left -13
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6]
right -12
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27]
left 84
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27]
right -8
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
left 77
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
right 53
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
[21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
94
为什么不直接使用需要 O(n) 时间的 Kadane 算法?
卡丹算法(DP):
Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
我会用一个小例子来说明你的算法有什么问题。
假设输入是
[2, -3, 1]
[2]
显然是最大子数组。但是,您的算法将查看此部分:
[2, -3, 1]
^^^^^
并看到它可以通过删除 [2, -3]
.
来增加数组的总和
如果最大子数组是负子数组的一部分,则从末端删除负子数组会做错事。您需要更智能的算法。
def contiguous(list_val, size):
if size<=len(list_val):
iterations = len(list_val)-size+1
count = 0
num = []
for i in range(iterations):
sum_val = 0
for j in range(count,size):
sum_val+=list_val[j]
num.append(sum_val)
count +=1
size +=1
print(max(num))
else:
print("Error: given size {} is greater than length of list".format(size))
list_val = input("Enter list: ")
size = input("Enter the pos: ")
contiguous(list_val, size)
试试这段代码。这适用于 O(n) 时间复杂度,因为它只运行了 n 次。
def manSubArraySum(a):
currentbest = 0
overallbest = a[0]
for p in a: # [1,2,-2,4]
currentbest = currentbest+p # first step cb = -10
if currentbest> overallbest: # !true
overallbest = currentbest
if currentbest<0: # nottrue
currentbest =0 # 0
return overallbest
今天刚开始学习Python,对它的功能不是很了解。然而,我发现了最大子数组问题,并想尝试用我掌握的几个简单的逻辑命令来解决它。我被卡住了,几乎可以肯定问题出在我的逻辑上而不是语法上,尽管我很可能是错的。到目前为止,这是我的代码...
def maxSequence(arr): #Latest attempt, some issue.
old_arr = []
print(arr)
while old_arr != arr:
old_arr = arr
if arr[0] > 0 and arr[len(arr)-1] > 0: #For when both sides are positive, need to be sure there is not anything to be gained by eliminating some side section
new_sum = 0
y=0
while new_sum >= 0 and y != -1:
new_sum = sum(arr[:y])
y=y+1
if y == len(arr)-1:
y=-1
if y != -1:
arr = arr[y-1:]
print("left %s" %(new_sum))
print("left %s" % (arr))
new_sum = 0
y = 0
while new_sum >= 0 and y != -1:
new_sum=sum(arr[(len(arr)-y):])
y=y+1
if y == len(arr)-1:
y=-1
if y != -1:
arr = arr[:len(arr)-y+1]
print("right %s" %(new_sum))
print("right %s" % (arr))
else:
while arr[0] < 0 or arr[len(arr)-1] < 0: #To eliminate negatives on sides
if arr[0] < 0:
arr = arr[1:]
if arr[len(arr)-1] < 0:
arr = arr[:len(arr)-1]
print("negative %s" % (arr))
print(arr)
print(sum(arr))
各种打印函数显示程序做出的每个决定,并帮助我可视化执行循环时发生的事情。
给出列表时没有给出正确的结果 105
[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26]
最终总和为 94,已将列表缩减为
[21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
很抱歉 post,但我就是想不通我做错了什么。预先感谢您的帮助!
这是将上述列表作为输入时的输出,我已经检查并查看了每一步,列表中的每一项删除对我来说都是合乎逻辑的,我不知道怎么会得到一个结束总和为105。如果有人能帮助我理解,我将不胜感激!
[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25,
-27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10,
-25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26]
negative [26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25,
-8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28,
11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17]
left -22
left [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15,
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17]
right -8
right [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15,
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25, -22, 8, 9, -4]
negative [3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15,
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25, -22, 8, 9]
left -3
left [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11,
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6,
-13, -13, 25, -22, 8, 9]
right -5
right [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11,
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6,
-13, -13, 25]
negative [15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11,
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6,
-13, -13, 25]
left -5
left [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6, -13, -13, 25]
right -1
right [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27,
-18, 6]
negative [1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18,
6]
left -13
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6]
right -12
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27]
left 84
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27]
right -8
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
left 77
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
right 53
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
[21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
94
为什么不直接使用需要 O(n) 时间的 Kadane 算法?
卡丹算法(DP):
Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
我会用一个小例子来说明你的算法有什么问题。
假设输入是
[2, -3, 1]
[2]
显然是最大子数组。但是,您的算法将查看此部分:
[2, -3, 1]
^^^^^
并看到它可以通过删除 [2, -3]
.
如果最大子数组是负子数组的一部分,则从末端删除负子数组会做错事。您需要更智能的算法。
def contiguous(list_val, size):
if size<=len(list_val):
iterations = len(list_val)-size+1
count = 0
num = []
for i in range(iterations):
sum_val = 0
for j in range(count,size):
sum_val+=list_val[j]
num.append(sum_val)
count +=1
size +=1
print(max(num))
else:
print("Error: given size {} is greater than length of list".format(size))
list_val = input("Enter list: ")
size = input("Enter the pos: ")
contiguous(list_val, size)
试试这段代码。这适用于 O(n) 时间复杂度,因为它只运行了 n 次。
def manSubArraySum(a):
currentbest = 0
overallbest = a[0]
for p in a: # [1,2,-2,4]
currentbest = currentbest+p # first step cb = -10
if currentbest> overallbest: # !true
overallbest = currentbest
if currentbest<0: # nottrue
currentbest =0 # 0
return overallbest