Lesson 7: MaxProfit (Max Profit)

Lesson 7: MaxProfit
https://codility.com/programmers/lessons/7

この問題はmax-sliceの問題に翻訳すればとけます。

ある連続した二日間で売買した場合の利益・損失は前日との株の価格の差になりますよね。そうすると、更に一日延ばしてそこで売る場合、初日と二日目の価格の差額と二日目と三日目の価格の差額を足したものが、初日で買い、三日目で売った場合の利益・損失になりますね。

こう考えると前日との差額の合計を考えて、そのmax sliceが最大の利益になりますね。

この方針で１００％のスコアがもらえます。

int solution(int A[], int N) 
{
    int max_ending = 0;
    int max_slice  = 0;

    int i;
    
    for (i = 1; i < N; i++){
        int diff = A[i] - A[i - 1];
        int tmp = max_ending + diff;
        max_ending = tmp < 0 ? 0 : tmp;
        max_slice  = max_slice < max_ending ? max_ending : max_slice;
    }

    return max_slice;
}