정확히 빈 하위 배열이란 무엇입니까?

Question

나는 운동 4.1-4 에 대한 질문을 알고리즘에 소개한다 :

최대 하위 배열 문제의 정의를 변경하여 빈 서브 어레이의 값의 합계가 0 인 빈 서브 어레이가되도록 허용한다고 가정합니다. 비어 있지 않은 알고리즘을 어떻게 변경합니까? 빈 서브 러 레이를 결과로 허용하는 하위 어레이는 무엇입니까?

빈 하위 배열

가 무엇인지 알 수 없습니다.

배열이 음수로 구성된 경우 하나의 숫자를 반환 할 수있는 점을 가로 지르 셨습니다.

빈 하위 배열의 개념을 설명 할 수 있습니까? 그리고 어떻게 빈 하위 배열을 가질 수 있습니까?

단일 요소가 반환 되더라도 여전히 하위 배열이 비어 있지 않음을 의미합니다. 의심의 여지가 없어주세요.

편집 :

요소의 배열을 취하는 경우 질문으로 더 명확하게하십시오.

[-3,-4,-1,-8]

.

대답은 -1 또는 0가 될 것입니까? 왜 0가되어야하는지 설명하고 어떻게 우리는 빈 하위 배열을 결론지게 할 수 있습니다.

고맙습니다.

Answer 1

이 배열이있는 경우 $ [- 2, -10, -5] $ 이고 문제는 해당 항목으로 돌아가야합니다. 최대 하위 배열 은 적어도 $ 1 $ 의 합계를 반환합니다. $ [-2] $ $-2 $ 인 $ . 지금까지 그렇게 좋습니까?

이제는 여기에 가장 문제가있는 곳입니다.

이제 문제가 조정됩니다. 이제 문제가 해당 문제가 빈 서브 어레이로 돌아갈 수 있습니다. 이는 빈 요소가없는 Subarray 인 Subarray로 돌아갈 수 있습니다. 나와 함께 곰 :

수학에서 "빈 합계"는 용어 수가 0 인 합계입니다. 확인.

마찬가지로, 컴퓨터 과학에서 "빈 서브 러 레이"는 용어 수가 0 인 서브 어레이입니다. 이것은 정의 일뿐입니다. 합계가 0으로 평가되는 소형 일뿐입니다.

이제, 문제의 조정 된 버전에 관한, $ [- 2] $ 에 반환하는 것은 $-2 $ 또는 빈 SubArray $ ([\ \ \]) $ 을 반환하는 것은 $ 0 $ ?

Answer 2

길이가 0의 서브 어레이가 비어 있습니다.

배열 $ a [1], \ ldots, [n] $ , 쌍의 인덱스 $ i \ leq j $ . 이들은 Subarray $ a [i], \ ldots, 길이 $ j-i + 1 $ . $ j= i-1 $ 을 허용하면 $ j-i + 1= 0 $ , 누구의 합이 0입니다.

---

최대 Subarray 문제에서는 $ a [1], \ ldots, [n] $ 을 제공하고, Subarray를 찾고 싶습니다. 합계는 최대입니다. 우리가 빈 서브 어레이를 허용하지 않으면, 이것은 우리가 최대 값을 찾고 있다는 것을 의미합니다. $$ A [I] + \ CDOTS + A [J], $$ 여기서 $ 1 \ LEQ I \ LEQ J \ LEQ N $ . 우리가 빈 서브 어레이를 허용하는 경우 $ 0 $ 으로 최대한의 최대 값을받습니다.

어레이의 모든 항목이 음수이면 전용 차이가 있습니다. 비어있는 비어있는 서브 어레이의 최대 합계는이 경우 최대 요소 $ a [i] $ , 이는 Subarray $ a [i] $ $ 1 $ . 그러나 빈 서브 어레이는 $ 0 $ 을 갖습니다. 따라서 빈 서브 어레이가 허용되지 않으면 $ \ max_i a [i] $ 이면 $ 0 $ .