0

我试图实现最大子数组问题的Brute方法(clrs 4.1-2),我认为我(很容易)得到它:
PSEUDO-CODE:

BRUTE-MAX-SUB-ARR(A)

1. from = -1 , to = -1, TSUM = -infinity
2. for i=0 to A.length-2
3.  sum = 0
4.  for j=i to A.length-2
5.   sum = sum+ A[i]
6.    if (sum > TSUM)
7.     TSUM = sum
8.     from = i
9.     to = j
10.    return(from,to,TSUM)  

但是当它只返回一个元素时问题就来了(from = to),因此,我们应该考虑一个案例 when from = to,但这要么排除了有用的案例,要么包含了多余的案例。

示例:
如果输入是 1,-4,3,-4 那么它会返回一个错误的答案(就像只有 3 是第 3 个元素)。
任何帮助表示赞赏。
月亮

编辑:1)天数更改为 A.length
2)我想知道我们如何处理当 时的情况from = to,也有最大值sum
3)0改为sum在伪代码的第 5 行。

4

0 回答 0