최대 주식 수익 문제 (배열 최대 차이 문제)

최대 주식 수익 문제 (배열 최대 차이 문제)
문제 설명
시간 에 따라 순 위 를 매 기 는 주식 가격 을 배열 하고 i 번 째 위치의 요 소 는 i 번 째 거래 시의 주식 가격 입 니 다.현 재 는 한 번 만 살 수 있다 고 가정 하고 어느 순간 에 (한 개의 주식) 을 팔 수 있다 고 가정 합 니 다. 알고리즘 을 설계 하여 당신 이 얻 을 수 있 는 최대 수익 을 구 해 보 세 요. 만약 에 주가 가 증가 하지 않 으 면 수익 은 0 입 니 다.
O (n2) 해법
배열 의 모든 요 소 를 뒤의 모든 요소 와 비교 하여 가장 큰 차 이 를 가 진 한 쌍 을 선택 하 십시오.시간 복잡 도:
T(n)=(n−1)+(n−2)+......+1
O (nlogn) 해법
알고리즘 사상
나 누 어 다스 리 는 사상 으로 배열 을 반 으로 나 누 면 최대 수익 은 다음 과 같은 3 가지 상황 으로 나 뉜 다. - 전반 부 에서 사고 팔 고 - 후반 부 에서 사고 팔 고 - 전반 부 에서 사고 후반 부 에 팔 고 1 가지 와 2 가지 상황 에 대해 규모 가 줄 어 든 새로운 문제, 즉 우리 의 알고리즘 을 교체 하 는 것 이다.세 번 째 상황 에 대해 서 는 전반 부 에서 최소 원소 min 을 찾 아야 하고 후반 부 에 최대 원소 max 를 찾 아야 한다. 그러면 max - min 은 세 번 째 상황 에서 가능 한 가장 좋 은 방법 이다.
의사 코드

void stock(int K[], int startIndex, int endIndex){
    int length = endIndex - startIndex;
    if(1==length) return 0;
    if(2==length) return K[endIndex]-K[startIndex] > 0 ? K[endIndex]-K[startIndex] : 0;
    if(length>2){
        midIndex = (startIndex+endIndex)/2;
        min = findMin(K, startIndex, midIndex );
        max = findMax(K, midIndex+1, endIndex);
        mayGet = max(stock(K,startIndex,midIndex), stock(K,startIndex,midIndex), max-min);
        return mayGet > 0 ? mayGet : 0;
    }
}

복잡 도
T(n)=2∗T(n2)+n2+n2
풀이:
T(n)=O(nlogn)
O (n) 해법
알고리즘 사상
예비 처리 배열 은 배열 의 최대 부분 과 문 제 를 구 한 다음 에 최대 부분 과 풀이 알고리즘 을 사용 하여 이 문 제 를 해결 합 니 다.
단계:
예비 처리 배열
배열 의 모든 항목 을 붙 어 있 는 앞 항목 을 빼 고 첫 번 째 항목 은 0 으로 설정 합 니 다.주가 배열 을 주가 증가폭 배열 로 바 꾸 겠 다 는 뜻 이다.예:

K = [3,5,1,2,5,8,9,6]

처리 후

K = [0,2,-4,1,3,3,1,-3]

미리 처리 한 후에 원래 의 문 제 는 배열 의 최대 부분 과 문 제 를 구 하 는 문제 로 바 뀌 었 다.예 를 들 어 원수 조 에서 가장 큰 수익 은 9 − 1 = 8 이 고 예 처리 후의 수조 에서 1 이후 의 첫 번 째 원소 부터 9 에 대응 하 는 원소 까지 누적 하면 1 + 3 + 3 + 1 = 8 이다.이 중의 이 치 는 매우 간단 하 다. 예 처리 후의 수조 가 저장 한 것 은 바로 증 량 이기 때문에 두 원소 간 의 모든 증 량 을 누적 하여 얻 은 것 은 바로 두 원소 의 차 이 였 다.예비 처리 알고리즘 위조 코드:

void preProcess(int K[], int n){
    int i;
    i = n-1;
    while(i>0){
        K[i] = k[i]-k[i-1];
    }
    K[0] = 0;
}

최대 하위 세그먼트 와
그러면 최대 수익 의 문 제 는 배열 의 최대 부분 과 문 제 를 구 하 는 문제 로 바 뀌 었 고 최대 부분 과 다음 과 같은 알고리즘 을 사용 했다.의사 코드 먼저 보기:

void maxSegSum(int K[], int n){
    int i;
    int maxSum=-MAXINT;
    int tempSum=0;
    for(i=0; iif(tempSum>maxSum) maxSum = tempSum;
        if(tempSum<0) tempSum=0;
    }   
    print("max sub-segment sum is %f", maxSum);
}

알고리즘 설명: - 처음부터 끝까지 배열 을 옮 겨 다 니 며 두 개의 전역 변 수 를 유지 합 니 다. max Sum 기록 이 가장 좋 습 니 다. tempSum 기록 은 특정한 위치 에서 시작 하 는 부분 과 -tempSum 을 업데이트 할 때마다 max Sum 과 비교 하고 max Sum 보다 크 면 max Sum 을 업데이트 합 니 다.그리고 tempSum 이 0 보다 작은 지, 계속 누적 되 지 않 으 면 tempSum 을 0 으로 돌려 줍 니 다. -이렇게 배열 을 한 번 훑 어 본 후에 얻 은 max Sum 은 이 배열 의 가장 큰 부분 과.
알고리즘 총론

예비 처리 배열 은 최대 서브 세그먼트 와 문제 O (n) 로 전환 합 니 다.

상기 알고리즘 을 사용 하여 최대 서브 세그먼트 와 문제 O (n) 를 풀이 합 니 다.

시간 복잡 도
T(n)=O(n)+O(n)
즉:
T(n)=O(n)