인터뷰 준비중인 취업 희망자 입니다. 준비중에 이런 문제를 보았는데요…

You’re given an array containing both positive and negative integers and required to find the subarray with the largest sum (O(N) a la KBL). Write a routine in C for the above.

위키피디아에 찾아 보면,
http://en.wikipedia.org/wiki/Maximum_subarray_problem

다음과 같이 예제가 나와 있습니다.

“… For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.”

사실 문제 자체가 잘 이해가 안되는데요.. 쩝.. 꾸벅.. 죄송..TT
도대체 어떤 값을 구하라는건지 도통…

그래서 위키피디아의 파이썬 예제를 보고 값을 나열해 보면요…

x max_ending_here max_so_far

---

-2 0 0
1 1 1
-3 0 1
4 4 4
-1 3 4
2 5 5
1 6 6
-5 1 6
4 5 6

이렇게 나옵니다. the largest sum 이 6 인것은, 최종 max_so_far가 6이어서 그런가요? 그런데, contiguous subarray 라는 것이 무엇인지 전혀 감이 안잡힙니다. 어떻게, [4, −1, 2, 1]가 나오는 것인지요?

저도 궁금해 했던 문제 중 하나였는데 덕분에 답을 알았군요 ^^

일반적인 array가 contiguous array입니다. 다른 개념의 어레이는 sparse array, disjoint array 이런게 있죠.

인터뷰어는 아마 저 문제를 정답을 도출해 내는 것을 기대하진 않을겁니다. 다만 Sub-O(1)으로라도 잘 코딩해 내는지에 관심이 있을겁니다.

인터뷰 성공하시길 바랍니다!

contiguous subarray 라는것은 원래 array 안에서 만들어 낼수 있는 contiguous array를 말하는 겁니다. 예를 들자면 [1,2,3,4] 라는 array가 있을때 [1], [1,2], [1,2,3], [1,2,3,4], [2,3,4], [3,4], [4] 가 contiguous subarray 가 되겠지요. 즉 문제에서 묻는것은 contiguous element의 합이 가장 큰 array를 만들어 내라는 것입니다. 위에 문제에서 보자면 [4,-1,2,1]이 다른 contiguous subarray의 합보다 크기 때문에 답이 되는것이지요. 이 문제를 푸는 쉬운 방법은 모든 subarray를 시도 해보는것이고 조금 더 좋은 방법은 첨 시작점과 next element를 더할때마다 체크 하면서 시작점을 옮기는 방법이 있겠네요..

이제야 질문의 뜻을 잘 알겠습니다. 고맙습니다.

헉. sub-O(1) 아~니~죠~…

에서 전화인터뷰때 물어본 문제입니다.

어떻게.. 푸셨나요?

Kadane’s algorithm에서 O(N)을 구현하는 원리를 좀 설명해 주실수 없는지요… 처음부터 죽 더해가면서, 합이 음수일때 매번 0 (zero)로 초기화 하는데, empty subarray를 선택하는거다… 어쩌고저쩌고 하는데… 잘 이해가 가지 않습니다.
저는 원래 EE 전공에 모바일 디바이스 드라이버 쪽인데, 이런 질문이 나올런지요…? 제가 어떻게 하나 볼려고 내볼수도 있을것 같긴 한데요…

K-algorithm은 처음부터 모든것을 다 더하는것이 아니고 현재까지의 max를 계속 기억하다가 새로운 맥스가 생기면 그것을 새로 기억해 두는 방법입니다.. 그리고 더해가다가 합이 음수라는 것은 element를 중심으로 두 contiguous subarray 로 나누어 생각해볼수 있다는 것과 empty array도 subarray라는 점을 생각하시면 이해에 도움이 되지 않을까 싶습니다. 예를 들어 [..,1, 3, 5, -10, 4, 2, 1, …] 이라는 array가 있을때, -10 앞에 subarray의 max가 10보다 작다고 생각을 해보세요. 그 얘기는 -10을 포함한 subarray는 뒤로 어떤 subarray를 만든다고 하더라도 -10 을 포함하지 않은 subarray 보다 항상 작다는것을 의미 하겠지요. 그렇기 때문에 매번 0으로 초기화 하는것입니다. 위에 위키피디아는 index는 구하지 않고 최대값만 구하는 방법이니까 몇가지 다른 사이트를 찾아보면 index를 구하는 방법도 있을겁니다.

그리고 일단은 어플라이 하는 회사에 따라 그런 질문을 할지 않할지가 결정 될거 같습니다.. 다만 저는 EE쪽이 아니여서 EE쪽은 어떤 질문을 주로 하는지는 잘 모르겠군요. 그럼 인터뷰 잘보시기를 빕니다.

EE 출신이고 Device driver 관련 쪽 뽑는데서 이 질문 나왔었습니다.