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

차례

문제 정책

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

예

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

암호알고리즘

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까지의 배열. 즉, 순진한 접근 방식으로 내부 중첩 루프가 수행 한 작업을 미리 계산하고 있습니다. 따라서 최대 값을 직접 찾아 내부 중첩 루프를 대체 할 수 있습니다. 사전 계산 알고리즘은 다음과 같은 방식으로 작동합니다.

크기가 다음과 같은 maxSP라는 배열을 만듭니다. 학비는 배열과 변수 max를 지정하고 최소값으로 초기화합니다.
의 마지막 색인에서 시작 학비는 정렬.
1. 가격 [i]이 최대 값보다 큰 경우
  1. 최대 값을 가격 [i]으로 업데이트하고 maxSP [i]를 최소값으로 설정
2. 가격 [i]이 최대 값보다 크지 않은 경우
  1. 업데이트 maxSP [i] = max.
사전 계산 후, 순진한 접근 방식을 따르고 방금 만든 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;
    }
}

주식 문제를 매매하기 가장 좋은 시간을위한 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;
}

복잡성 분석

시간 복잡성

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

공간 복잡성

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

Twitter Facebook 링크드 인 버퍼 레딧 텀블러