首页 > 代码库 > 最大连续子串
最大连续子串
问题：一个由正数、负数、0组成的序列中，求一个连续子序列，使他们之和最大
解一：暴力法，直接求出所有可能，找出最大值
1 MAX_SEQ_SUM( A, len ) 2 max = A[0] 3 max_b = max_e = 0 4 5 for i -> 0:len-1 6 sum = 0 7 for j->i:len-1 8 if j == i then sum = A[i] 9 else sum += A[i]10 if sum > max then11 max = sum12 max_b = i13 max_e = j14 15 return max,max_b,max_e
复杂度为：O(n^2)
解法2：遍历数组时记录当前和，如果和大于最大值，则记录，如果和小于0，则从当前元素重新计算
MAX_SEQ_SUM(A,len) sum = max = A[0] max_b = max_e = 0 for i -> 1:len if sum < 0 then sum = A[i] ; b = e = i; else sum += A[i] ; e = i; if sum < max then max = sum ; max_b = b; max_e = e; return max,max_b,max_e
复杂度为：O(n)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。