최대 하위 배열 문제에서 $\binom{n-1}{2}$ 하위 배열의 관련성을 이해할 수 없습니다.

Question

나는 최근 책 소개 알고리즘 섹션에서 문장을 발견했습니다. 4.1 최대 하위 배열 문제:

아직 확인이 필요해요 $\binom{n-1}{2} = heta(n^2)$ 일정 기간 동안의 하위 배열 $n$ 날.

여기 $n$ 주식 가격의 변화를 보여주기 위해 예로 든 일수입니다.

이것이 배열 A의 크기라고 생각할 수 있습니다.

어레이 A가 제공되고 첫날부터 마지막 ​​날까지 순 변화가 최대임을 찾아야 합니다.

좀 더 구체적으로 설명하자면 배열을 의미합니다. $A$ 크기의 $n$ 우리는 확인해야 해 $\binom{n-1}{2}$ 하위 배열.

하지만 우리가 어떻게 필요한지 이해할 수 없습니다 $\binom{n-1}{2}$ 하위 배열?

크기 배열을 취하면 5 누군가 우리에게 왜 필요한지 설명해 주시겠어요? 6 하위 배열.하위 배열은 다음과 같지 않습니까?

[1...5]
[1...4]
[1...3]
[1...2]

[2...4]
[2...5]


[3...5]
[4...5]

내가 틀렸다면 정정해주세요.참고자료: 최대 하위 배열 문제

감사합니다.

Answer 1

당신은 컴퓨터 과학에 관한 가장 유명한 교과서 중 하나에서 버그를 발견했습니다!

---

있는 동안 $n$ 일, 밖에 없습니다 $n-1$ 주식 가격의 변화.그래서 있습니다 $\binom{n-1}{2}$ 하위 배열이 다른 인덱스에서 시작하고 끝난다고 가정하여 주식 가격 변동 배열의 하위 배열입니다.

내 생각엔 책에 "아직 확인이 필요하다"고 쓰여 있는 이유가 설명되어 있습니다. $\binom{n-1}{2} = heta(n^2)$ 일정 기간 동안의 하위 배열 $n$ 날".

---

하지만 사실 우리가 아직 확인해야 할 부분이 있다는 말씀이 맞습니다. $\binom n2$ 하위 배열.

허락하다 $B$ 일정 기간 동안의 일일 가격 배열이 됩니다. $n$, 인덱스(일) 0부터 시작합니다.허락하다 $A$, 책에서와 같이 인덱스(일) 1부터 시작하여 가격 변동에 해당하는 배열이 됩니다.당일 구매를 선택하신 경우 $i$ 그리고 당일에 팔아요 $j$, 이익을 창출하다 $B[j]-B[i]$, 하위 배열에 해당합니다. $A[i+1\,..\,j]$, 즉., $(A[i+1], A[i+2], \cdots, A[j])$.지수의 변화를 참고하세요 $i$ 그리고 $j$ ~에 $B$ 인덱스에 $i+1$ 그리고 $j$ ~에 $A$.하는 동안 $i$ 그리고 $j$ "한 단위의 주식을 한 번만 구매한 다음 나중에 판매할 수 있으므로" 항상 달라야 합니다. $i+1$ 그리고 $j$ 언제라도 똑같다 $j=i+1$, 즉, 다음날 매도할 때입니다.

선택한 숫자의 합을 확인해 보겠습니다. $A$ 정말이다 $B[j]-B[i]$. $$ begin {aligned} & quad a [i+1]+a [i+2]+ cdot+a [j] & = (b [i+1] -b [j])+( b [i+2] -b [i+1])+ cdot+(b [j] -b [j-1]) & = b [j] -b [i]. end {aligned} $ $공식은 다음과 같은 경우에 유지됩니다. $j=i+1$.

하위 배열 외에도 $A$ 서로 다른 인덱스에서 시작하고 끝나는 경우 시작 인덱스와 끝 인덱스가 동일한 하위 배열을 고려해야 합니다.있다 $n-1$ 즉, 유일한 요소가 있는 하위 배열은 $A[1]$, 유일한 요소가 있는 하위 배열 $A[2]$, ...유일한 요소가 있는 하위 배열은 $A[n-1]$.부터 $\binom{n-1}2+(n-1)=\binom n2$, 아직 확인이 필요합니다 $\binom n2$ 하위 배열.

예를 들어, 일정 기간 동안의 일일 가격이 $3$ 일은 $B=(85, 105, 102)$, 가격의 변화는 $A=(20, -3)$.하위 배열을 확인하지 않으면 $A$, $(20)$, 가격에 구매한다는 의미 $85$ 낮에 $0$ 그리고 가격에 팔아요 $105$ 낮에 $1$, 우리는 최적의 이익을 놓칠 것입니다. $20$.

---

이 간단하고 명백한 버그는 목록에 없습니다. 에 대한 정오표 페이지 알고리즘 소개, 세 번째 버전.당신이 명시적으로 지적하기 전까지 이 버그가 그 인기 있는 책에서 10년 넘게 편안하게 살아왔다는 것이 믿기지 않습니다.

반면에 나는 눈치 채지 못했지만 많은 사람들이 그 버그를 알고 있었을 것입니다.그 잘못된 진술의 초점은 "아직 확인이 필요하다"입니다. $\세타(n^2)$ 일정 기간 동안의 하위 배열 $n$ 날".확인해야 하는 실제 하위 배열 수는 점근적 증가 수준이 정확하다면 그다지 중요하지 않습니다.오해의 소지가 있는 반면, 해당 버그는 더 나은 알고리즘 개발에 큰 해를 끼치지 않습니다.