我试图实现最大子数组问题的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 行。