주식을 사고 팔기에 가장 좋은시기

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance 시스코 드 쇼 이베이 Expedia Facebook 골드만 삭스 구글 JP 모건 Microsoft 모건 스탠리 (Morgan Stanley) 신탁 페이팔 Qualtrics 삼성 VM웨어
배열 동적 프로그래밍조회수 31

문제 정책

“주식을 사고 팔기 가장 좋은시기”라는 문제는 정렬 길이 n의 가격, 여기서 i 번째 요소는 i 번째 날의 주식 가격을 저장합니다.
단 하나의 거래, 즉 하루에 매수하고 다음 날에 매도 할 수 있다면 최대 수익은 얼마가 될 것입니다.

prices[] = {7, 1, 5, 3, 6, 4}
5

암호알고리즘

i 번째 날에 주식을 매수하면 i + 1 ~ n 사이의 날에 주식을 매도하여 최대 이익을 얻습니다. 따라서 그 날은 주식의 최고 가격을 가지며 가격 [i]보다 높습니다.
가격 고려 = {7, 1, 5, 3, 6, 4}

주식을 사고 팔기에 가장 좋은시기
따라서 최대 이익은 2 일에 주식을 사고 5 일에 판매하면 얻을 수 있으며 최대 이익은 5입니다.

주식을 사고 팔기에 가장 좋은시기를위한 순진한 접근 방식

위의 알고리즘을 구현하는 순진한 접근 방식은 두 개의 중첩 된 루프를 실행하는 것입니다.

의사 코드

int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = price[i];
  int max = -infinity;
  // Finding the maximum stock price greater than costPrice on upcoming days
  for (int j = i + 1; j < n; j++) {
    if (prices[j] > costPrice) {
      max = maximum(max, a[j]);
    }
  }
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

복잡성 분석

시간 복잡성

O (n ^ 2), 왜냐하면 우리는 주식을 사고 파는 날을 선택하기 위해 두 개의 중첩 루프를 사용하기 때문입니다. 따라서 시간 복잡도는 다 항적입니다.

공간 복잡성

O (1), 데이터 구조의 각 요소에 대한 정보를 저장하지 않기 때문입니다. 우리는 일정한 공간만을 사용하고 있습니다. 따라서 공간 복잡성은 선형입니다.
여기서 n은 배열의 요소 수입니다.

주식을 사고 팔기 가장 좋은시기를위한 최적의 접근 방식

더 나은 접근 방식은 정렬 i 번째 요소는 현재 최대 값을 저장합니다. 학비는 인덱스 i + 1에서 n까지의 배열. 즉, 순진한 접근 방식으로 내부 중첩 루프가 수행 한 작업을 미리 계산하고 있습니다. 따라서 최대 값을 직접 찾아 내부 중첩 루프를 대체 할 수 있습니다. 사전 계산 알고리즘은 다음과 같은 방식으로 작동합니다.

  1. 크기가 다음과 같은 maxSP라는 배열을 만듭니다. 학비는 배열과 변수 max를 지정하고 최소값으로 초기화합니다.
  2. 의 마지막 색인에서 시작 학비는 정렬.
    1. 가격 [i]이 최대 값보다 큰 경우
      1. 최대 값을 가격 [i]으로 업데이트하고 maxSP [i]를 최소값으로 설정
    2. 가격 [i]이 최대 값보다 크지 않은 경우
      1. 업데이트 maxSP [i] = max.
  3. 사전 계산 후, 순진한 접근 방식을 따르고 방금 만든 maxSP 배열을 사용하여 내부 중첩 루프를 교체합니다.

의사 코드

// Pre computation
int max = -infinity;
for (int i = n - 1; i >= 0; i--) {
  if (prices[i] > max) {
    max = prices[i];
    maxSP[i] = -infinity;
  } else {
    maxSP[i] = max;
  }
}
// Do as in naive approach
int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = prices[i];
  // Rather than using a loop to calculate max, we can directly get it from maxSP array
  int max = maxSP[i];
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

암호

주식 문제를 사고 팔기 가장 좋은시기를위한 자바 코드

import java.util.Scanner;

class BestTimetoBuyandSellStock {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // Prices array
        int prices[] = new int[]{7, 1, 5, 3, 6, 4};

        // Calculating the max profit
        int ans = maxProfit(prices, prices.length);

        // Print the answer
        System.out.println(ans);
    }

    private static int maxProfit(int[] prices, int n) {
        int maxSP[] = new int[n];
        int max = Integer.MIN_VALUE;

        // Construct the maxSP array
        for (int i = n - 1; i >= 0; i--) {
            if (prices[i] > max) {
                max = prices[i];
                maxSP[i] = Integer.MIN_VALUE;
            } else {
                maxSP[i] = max;
            }
        }

        int profit = 0;
        for (int i = 0; i < n; i++) {
            if (maxSP[i] != Integer.MIN_VALUE) {
                profit = Math.max(profit, maxSP[i] - prices[i]);
            }
        }

        // Return profit
        return profit;
    }
}
5

주식 문제를 매매하기 가장 좋은 시간을위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int maxProfit(int *prices, int n) {
    int maxSP[n];
    int max = INT_MIN;
    
    // Construct the maxSP array
    for (int i = n - 1; i >= 0; i--) {
        if (prices[i] > max) {
            max = prices[i];
            maxSP[i] = INT_MIN;
        } else {
            maxSP[i] = max;
        }
    }
    
    int profit = 0;
    for (int i = 0; i < n; i++) {
        if (maxSP[i] != INT_MIN) {
            profit = std::max(profit, maxSP[i] - prices[i]);
        }
    }
    
    // Return profit
    return profit;
}

int main() {
    // Prices array
    int prices[] = {7, 1, 5, 3, 6, 4};
    
    // Calculating the max profit
    int ans = maxProfit(prices, sizeof(prices) / sizeof(prices[0]));
    
    // Print the answer
    cout<<ans<<endl;
    return 0;
}
5

복잡성 분석

시간 복잡성

의 위에), 최대 이익을 미리 계산하고 계산하는 동안 배열의 n 개 요소를 순회했기 때문입니다. 시간 복잡도는 선형입니다.

공간 복잡성

의 위에), 사전 계산 부분에서 오늘 다음날 최대 판매 가격을 저장했기 때문입니다. 배열의 모든 요소에 대해 저장되기 때문입니다. 공간 복잡성도 선형입니다.
여기서 n은 배열의 요소 수입니다.

Translate »