最大サブアレイ問題 (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)
しかし、それが返す要素が 1 つだけの場合に問題が発生する(from = to)ため、 の場合を考慮する必要がありますfrom = toが、これには有用なケースが除外されるか、冗長なケースが含まれます。
例 :
入力が 1,-4,3,-4 の場合、間違った答えが返されます (3 番目の要素である 3 のみなど)。
どんな助けでも感謝します。
月
編集: 1) 日が A.length に変更されました2)最大値が で
ある場合の処理方法を知りたかったのです。
3)疑似コードの行番号 5 に変更されました。from = tosum0sum