若序列 X={1, 2, -2, 3, -3, 1, -3,

[填空题]

若序列 X={1, 2, -2, 3, -3, 1, -3, 2, 2, -2, 3, -2, 3, -2}，则该序列的所有连续子序列中，连续子序列内各元素和的最大值为1。

(说明: 连续子序列指原序列中若干连续元素构成的序列，所有子序列中最短长度1，最大长度即原序列的长度。例如第3，4，5号连续的元素就是一个连续子序列，其元素为{-2, 3, -3}，各元素和为-2+3-3=-2)

查看正确选项

DGZI

取两个指针，一个从小到大，一个从大到小，进行遍历，这样时间复杂度最低

发表于 2018-06-15 18:39:03 回复(2)

一厘米天气晴

1, 2, -2, 3, -3, 1, -3, 2, 2, -2, 3, -2, 3, -2

发表于 2017-08-26 15:09:24 回复(0)

NewPerson

用一个max记录最大连续和，用一个sum 记录遍历的和，从左到右遍历数组，遍历到下标 i 时，sum += arr[i]，如果sum>0，则sum = sum，如果sum小于0，则sum = 0，判断更新max的值，遍历结束后的max即为所求。

int max = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < arr.length; i++) {
    sum += arr[i];
    if (max < sum) {
         max = sum;
   }
   sum = sum > 0 ? sum : 0;
}

发表于 2017-09-02 22:34:17 回复(4)

小小趴菜

def count_max(a):
    max_sum = [] 
    for i in range(len(a)):
        m = 0
        b = []
        for j in range(i,len(a)):
            m+=a[j]
            b.append(m)
        max_sum.append(max(b))
    return (max(max_sum))

a=[1, 2, -2, 3, -3, 1, -3, 2, 2, -2, 3, -2, 3, -2]
print(count_max(a))

用了暴力循环，先依次计算a[0],a[0]+a[1],a[0]+a[1]+a[2],.....直到a[0]+...a[13]的共13个值存到数组b中，然后取b中最大值放到max_sum数组中，i+1=1,从a[1]开始执行上述过程，。。。最外层循环结束时共得到13个值放到数组max_sum中，然后求数组max_sum的最大值，即最终结果。

发表于 2019-09-21 10:05:20 回复(0)

Xavier25

构建一个n*n的二维矩阵，行表示位置，列表示子序列长度，最终得到一个上三角矩阵，计算复杂度n平方的一半

发表于 2019-03-29 10:18:39 回复(0)

有马公生

算法核心：最大的连续序列的第一号值一定不为负（该序列所有元素都为负的可能性除外），因为最大连续序列第一号值如果为负的话，可以直接去掉，使序列和变大，所以假设我们获取了一个序列，要使它变大可以在序列前加前缀序列，在序列后扩张序列。解题：max 记为最大连续序列的和初始值为0，sum 记为后缀序列的和初始值为0，我们从该序列的第一号元素开始循环遍历，sum +=arr [i]，如果sum >max 则将sum 赋给max ，相当于我们找到一个max 连续序列，在此基础上对序列进行后缀扩张，当循环到某个i时，sum <0，即前i个序列中的最大序列和值已被max记录，而且将前i个序列看成一个前缀序列，它的和为负的，不能成为最大序列的前缀，接下来的步骤相当于在i以后的序列里在此寻找有没有比前i个里面更大的序列和。仅以此记下自己的理解

编辑于 2018-10-01 11:57:11 回复(0)