#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct DealRecord {  // 單筆買賣記錄
  int buyD;  // 購買日
  int sellD;  // 賣出日
  double minP;  // 購買日 Price
  double maxP;  // 賣出日 Price
  double profit;  // 獲利
};

struct DealRecord findMaxProfit(const double * const price, int head, const int tail) {
  struct DealRecord prevDeal = {-1, -1, INT_MAX, INT_MAX, 0};
  struct DealRecord bestDeal(prevDeal);

  while (head < tail) {
    if (price[head] < price[head+1]) {  // head is 相對低點 -> head is buyDay
      int sellDay = head + 1;
      while (1) {
        if (sellDay == tail || price[sellDay] > price[sellDay+1]) {  // sellDay is 相對高點
          if (price[head] <= prevDeal.minP) {
            // (new) prevDeal = current deal
            prevDeal.buyD = head; prevDeal.sellD = sellDay;
            prevDeal.minP = price[head]; prevDeal.maxP = price[sellDay];
            prevDeal.profit = prevDeal.maxP - prevDeal.minP;
          } else {
            if (price[sellDay] > prevDeal.maxP) {
              // (new) prevDeal = current deal + prevDeal (合併)
              prevDeal.sellD = sellDay; prevDeal.maxP = price[sellDay];
              prevDeal.profit = prevDeal.maxP - prevDeal.minP;
            }
          }
          if (prevDeal.profit > bestDeal.profit)  bestDeal = prevDeal;
          break; // 找新的購買組合 -> 繼續移動 head
        }
        ++sellDay;
      }
    }
    ++head;
  }
  return bestDeal;
}

int main() {
  void setRandomCase(double *, int);
  
  // double price[] = {40, 70, 25, 35, 26, 28, 27, 29, 28, 30, 65, 10, 20};  // case 1
  // double price[] = {55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};  // case 2 
  // double price[] = {55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24};  // case 3
  double price[15];  // case Random
  setRandomCase(price, sizeof(price) / sizeof(double));

  struct DealRecord bestDeal = findMaxProfit(price, 0, sizeof(price) / sizeof(double) - 1);
  printf("最佳買日：%d\t價格：%f\n"
         "最佳賣日：%d\t價格：%f\n"
         "\t\t利潤為：%f\n", 
         bestDeal.buyD + 1, bestDeal.minP, 
         bestDeal.sellD + 1, bestDeal.maxP, 
         bestDeal.profit);
  return 0;
}

void setRandomCase(double *arr, int num) {
  srand( (unsigned int) time(NULL));
  printf("double price[%d] = {", num);
  for (int i = 0; i < num; ++i) {
    arr[i] = (double) (rand() % 1000);
    printf("%d", (int) arr[i]);
    if (i != num-1) printf(", ");
  }
  printf("};  // case Random\n\n");
}

double price[15] = {631, 477, 350, 449, 896, 196, 806, 961, 211, 512, 435, 683, 538, 461, 623};  // case Random

最佳買日：6	價格：196.000000
最佳賣日：8	價格：961.000000
		利潤為：765.000000