Maximum subarray sum
Codewars Kata 31√
Description
https://www.codewars.com/kata/54521e9ec8e60bc4de000d6c
-简述：本题给定一列数字，求出数字相加之和最大的子序列，返回最大的sum值。
-思路：从头到尾遍历数列，不断替换max的值，找到最大的sum
The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:
maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) should be 6: [4, -1, 2, 1]
Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.
Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.
My solution
def maxSequence(arr):
if arr == []:
return 0
else:
a = []
for i in range(0,len(arr)):
for j in range(0,len(arr)):
sum2 = sum(arr[i:j+1])
a.append(sum2)
return max(a)
print(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
Given solutions
def maxSequence(arr):
max,curr=0,0
for x in arr:
curr+=x
if curr<0:curr=0
if curr>max:max=curr
return max
def maxSequence(arr):
lowest = ans = total = 0
for i in arr:
total += i
lowest = min(lowest, total)
ans = max(ans, total - lowest)
return ans
def maxSequence(arr):
maxl = 0
maxg = 0
for n in arr:
maxl = max(0, maxl + n)
maxg = max(maxg, maxl)
return maxg
Points
1 我的方法遍历次数较多，虽然没有超时，但是不够快。
