[C] 최대 이익을 내는 시기를 찾아내는 알고리즘

연속하는 날들에 대하여 각 날의 주식 가격이 주어져 있다. 이때 어떤 날에 주식을 산 후, 최대 이익을 남기며 이후의 날에 팔고자 한다. 어떤 날에 사서 어떤 날에 팔면 되는가?

두 가지 방법으로 해결하라.

방법 1: O(n2) 시간의 알고리즘

방법 2: 분할과 정복을 이용한 O(n log n) 알고리즘


입력 예

3 // 날 수
9 1 5 // 첫째 날 주식 가격: 9, 둘째 날 주식가격: 1, 셋째 날 주시가격: 5

출력 예

사는 날: 2일째
파는 날: 3일째





test 화일을 올려놉니다.

invalid-file

저는 O(n)의 속도로 탐색하는 알고리즘을 생각했습니다.
매우 빠른 속도로 동작하며, min , max 값의 원리를 이용하였습니다.

data : int 배열
len : 배열의 길이
buy : 주식을 사야하는 날 저장 공간
sell : 주식을 팔아야하는 날 저장 공간

중요 함수 부분입니다.

int find(int* data , int len , int* buy , int* sell)
{
int min = -1; int max = -1; int tmp = -1; int i_tmp = -1;

// data를 순차적으로 순환하며 자료을 읽어 처리합니다.
for (int i = 0 ; i < len ; i++)
{
// 첫자료는 min과 tmp에 저장합니다.
// 이때 index값이 날짜와 일치합니다.
if (i == 0)
{
min = data[i]; *buy = i;
tmp = data[i]; i_tmp = i;
}
else
{
// Min값보다 작고 tmp값보다 작은지를 확인
if ( (data[i] < min) && (data[i] < tmp) )
{
if (data[i] > max)
{
// Min값으로 확정
min = data[i]; *buy = i;
tmp = data[i]; i_tmp = i;
}
else
{
// 임시로 tmp 저장
tmp = data[i]; i_tmp = i;
}
}
// Min나 tmp 값보다는 크기에 Max값보다 큰지를 검사
else if (data[i] > max)
{
max = data[i]; *sell = i;
if (tmp != -1)
min = tmp; *buy = i_tmp;

}
// 차이가 임시 저장한 것이 더 큰 이익이라면
else if ( (data[i]-tmp) > (max-min) )
{
min = tmp; *buy = i_tmp;
max = data[i]; *sell = i;
}
}
}

return max - min;
}