最佳交易

知道每日金价，希望从中找出两个交易日，在第一个交易日买进，第二个交易日卖出，能实现利润最大化。

#include "pch.h"
#include <iostream>
#include <vector>
#include <time.h>

const size_t INVALID_POS = -1;

std::pair<size_t, size_t> GetTradePos(const std::vector<int>& prices) {
    if (prices.size() < 2) {
        //个数小于2，找不出买卖点
        return std::make_pair(INVALID_POS, INVALID_POS);
    }
    else if (prices.size() == 2) {
        if (prices[0] >= prices[1]) {
            //没有利润，找不出买卖点
            return std::make_pair(INVALID_POS, INVALID_POS);
        }
        else {
            return std::make_pair(0, 1);
        }
    }

    int max_gain = 0;
    int buy_pos = INVALID_POS;
    int sell_pos = INVALID_POS;
    for (int i = 0; i < prices.size() - 1; i++) {
        for (int j = i + 1; j < prices.size(); j++) {
            if (prices[j] - prices[i] > max_gain) {
                max_gain = prices[j] - prices[i];
                buy_pos = i;
                sell_pos = j;
            }
        }
    }

    return std::make_pair(buy_pos, sell_pos);
}

int main()
{
    std::vector<int> prices;
    srand(time(nullptr));

    for (int i = 0; i < 50; i++) {
        int rand_num = rand();
        prices.push_back(rand_num);
    }

    auto ret = GetTradePos(prices);
    return 0;
}