심심해서 풀어본 알고리즘 문제 하나.

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.

한번 훓어서 가장 크기가 큰 Subarray의 인덱스를 찾아내면 될거 같다.

아래 포스팅이 너무 눈에 거슬려서 문제하나  풀어봤다.
풀어본다음에 구글 검색을 해보니 비슷한 방법으로 C++로 풀어본 사람이 있더라.
rand 함수로 음수를 제너레이트 하기 위해 꽁수 부린것… 그것 빼놓고는 비슷한거 같다.

문제 대로 C로 풀어봤다.

XTGnoWUlXz.c

위의 것을 그래프로 표현을 해보면(x : 배열 인덱스, y : sum) 증가하다가 감소하는 부분까지의 합계가 가장 큰 부분을 찾으면 되겠다. 값이 크면 인덱스 업데이트, 업데이트 계속 하면서  (아니면 그대로 끝나든지 하는 부분…)

max값을 update하면서 인덱스도 동시에 저장하면서 나아가면 한번에 끝난다.

다른 좋은 방법있으면 소개시켜주길 바란다.

ps. 문제중에 “la KBL”이 무슨 말인지 잘 모르겠다.