C++에서 주식을 사고 팔 때 최대 이익

이 문제에서 i번째 날의 특정 주식 가격을 나타내는 배열 stkprice[]가 제공됩니다. 우리의 임무는 C++에서 주식을 사고 팔고 난 후 최대 이익을 계산하는 프로그램을 만드는 것입니다.

문제 설명 − 여기서 이익을 얻으려면 주식을 언제 사서 팔 수 있는지 확인해야 합니다. 이익을 얻으려면 낮은 가격에 주식을 사서 가격이 오를 때 팔아야 합니다. 그리고 드롭이 다시 발생하면 동일하게 반복하십시오.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

stkprice[] = {120, 310, 405, 210, 150, 550}

출력

685

설명

1일차에 매수하고 3일차에 매도하면 285의 이익이 발생합니다.

이후 5일차에 매수하고 6일차에 매도하면 400의 이익이 발생합니다.

이것은 (400 + 285) =685의 총 이익을 만듭니다.

솔루션 접근 방식

간단한 솔루션은 매수-매도 주기의 가능한 모든 조합을 확인하는 것입니다. 오늘의 마지막 매수 매도부터 매수 매도까지의 매수-매도 사이클 조합을 시도해보세요. 그리고 그 최대의 이익을 가져다주는 사이클을 취합니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <iostream>
using namespace std;
int max(int a, int b){
   if(a > b)
      return a;
      return b;
}
int MaximizeProfit(int stkPrice[], int firstDay, int lastDay){
   if (lastDay <= firstDay)
      return 0;
   int maxProfit = 0;
   for (int i = firstDay; i < lastDay; i++) {
      for (int j = i + 1; j <= lastDay; j++) {
         if (stkPrice[j] > stkPrice[i]) {
            int profit = ( stkPrice[j] - stkPrice[i] ) + MaximizeProfit(stkPrice, firstDay, i - 1) + MaximizeProfit(stkPrice, j + 1, lastDay);
            maxProfit = max(maxProfit, profit);
         }
      }
   }
   return maxProfit;
}
int main(){
   int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
   int days = 6 ;
   cout<<"The Maximum profit is "<<MaximizeProfit(stkPrice, 0, days);
   return 0;
}

출력

The Maximum profit is 4196007

보다 효과적인 솔루션은 각 거래에 대한 최대 이익을 찾아 그들로부터 최대 이익을 찾는 것을 기반으로 합니다. 이것은 거래일에 대한 지역 최소값과 최대값을 구하여 수행할 수 있습니다. 로컬 최소값은 주가가 전날과 다음 날 모두보다 낮은 날입니다. Andmaxima는 최소값과 반대입니다. 극소값이 없으면(index0 ~ n-2 이내) 수익이 날 수 없습니다.

이익을 최대화하기 위해 우리는 지역 최소값에서 주식을 사서 다음 지역 최대값에서 매도하고 최소값-최대값 쌍에 대해 동일한 작업을 수행합니다. 모든 최소-최대 이익을 더하면 maxProfit이 됩니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <iostream>
using namespace std;
void MaximizeProfit(int price[], int n){
   if (n == 1)
      return;
   int maxProfit = 0;
   int i = 0;
   while (i <= n - 1) {
      while ((i <= n - 2) && (price[i + 1] <= price[i]))
         i++;
         int minima = i++;
      while ((i < n) && (price[i] >= price[i - 1]))
         i++;
      int maxima = i - 1;
      maxProfit += (price[maxima] - price[minima] );
      // For displaying profit for one minima-maxima cycle
      //cout <<"Stock bought on day "<<(minima+ 1 )<<" and Sold
      on day "<<(maxima+1) <<" at a profit of "<<(price[maxima] - price[minima] )<<"\n";
   }
   cout<<"The maximized profit is "<<maxProfit;
}
int main(){
   int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
   int days = 6;
   MaximizeProfit(stkPrice, days);
   return 0;
}

출력

The maximized profit is 685