[LeetCode] Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

주어진 배열에서 value 차가 가장 큰 경우를 구하는데, 뺄 때 큰 수는 index가 작은 수보다 뒤여야 한다.

처음에는 단순히 2중 선형 탐색으로 풀까 하다가, 조금 빠른 방법이 없을까 하여 value 및 index 기준으로 정렬한 후에 탐색을 돌리고 탈출하는 로직을 생각했다.

다만, 처음 생각보다 많이 빨라지지는 않아, C#으로 현재값/현재까지최소값/이득 으로 나누어 푸는 풀이로도 풀어보았다.

struct muzi {
    int value;
    int index;
};
    
bool cmpValue(struct muzi source, struct muzi compare) {
        if(source.value>compare.value)
            return true;
        else if(source.value==compare.value && source.index>compare.index)
            return true;
        else 
            return false;
}
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result=0;
        int size = prices.size();
        if(size<1)
            return 0;
        vector<muzi> sortedPrices(size);
        for(int i=0;i<size;i++) {
            muzi temp;
            temp.value=prices[i];
            temp.index=i;
            sortedPrices[i]=temp;
        }
        sort(sortedPrices.begin(),sortedPrices.end(),cmpValue);
        
        for(int i=size-1;i>0;i--) {
            muzi source = sortedPrices[i];
            if(i<size-1&&(source.index>sortedPrices[i+1].index))
                continue;
            for(int j=0;j<i;j++) {
                if(sortedPrices[j].value==0)
                    continue;
                if(source.index<sortedPrices[j].index && result < sortedPrices[j].value-source.value) {
                    result=sortedPrices[j].value-source.value;
                }
            }
        }
        
        return result;
    }
    
   
};

해도해도 잘 풀기는 어려운 것 같다.