株式の利益を最大化する（最大サブアレイ）

Question

"Introduction To Algorithms"を読んでいます。最大部分配列問題（第4章）では、配列の最大値と最小値を見つけるだけで、株式の売買の最大利益を計算することはできないと主張しています。著者は、0（n^2）時間が必要な購入日と売り日の可能な組み合わせをすべて計算することにより、ブルートフォースなどの代替案を話します。もう1つの選択肢は、価格配列の日々の変化の最大部分配列を見つけることです。

しかし、私は0（n）時間かかると最大利益を見つけるアルゴリズムをコーディングしました。これは0（n）であり、最大のサブアレイ問題は0（n log n）である。しかし、私は著者が間違っていることはできないことを知っています。どこが間違っていますか？私のアルゴリズムは正しいですか？

#include <stdio.h> 
#include <limits.h> 

int main(void) 
{ 
    int A[8]={10,8,3,9,7,4,5,10,4}; 
    int i,max,min,currmax,prevmax,n=8; 

    max=INT_MIN; 
    min=INT_MAX; 
    for(i=0;i<n;i++) 
    { 
     if(A[i]>max) 
     { 
      max=A[i]; 
      prevmax=currmax; 
      currmax=max-min; 
     } 
     if(A[i]<min) 
     { 
      min=A[i]; 
      max=INT_MIN; 
     } 

    } 

    if(prevmax>currmax) 
     printf("%d",prevmax); 
    else 
     printf("%d",currmax); 

    return 0; 
} 

GeeksForGeeksに示すよう

---

（http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/）、株価の日々の変化のための入力は、[] = { - 2、-5、6、-2、-3、1、5、 -6}である。 私は基本価格を10とし、アルゴリズムをA [] = {10,8,3,9,7,4,5,10,4}として実行しました。

入力：10,8,3,9,7,4,5,10,4

出力：7

Answer 1

ここにあなたがあなたが売買を通じて行うことができる最大の利益を探していますストック（一度重要です）。

あなたのアルゴリズムでは、株式の最低ストライキ価格から最高の利益が生じると仮定しています。 これは間違っている：A[] = {10,23,6,12,4,1,0,3}、プログラムの出力3と、例えば最大の利点は、明らかに13であるのに対し（Coliruにプルーフ）

最適な利益の特徴ストック固定具のデルタ配列を計算することである（A[ ]={-2, -5, 6, -2, -3, 1, 5, -6}あなたが引用した配列）、最大部分配列を取得します。私の例ではF[] = {13, -17, 6, -8, -3, -1, 3}、最大サブアレイは{13}です。結局、必要な利益は最大サブアレイの合計です。

もう1つの方法は、配列の最小値のタブを反復して保持することです。A[0..i-1]（iは1からn-1の範囲です）。インデックスi（すなわち、時刻iでの販売）では、差額がA[i] - min(A[0..i-1])、またはその差がマイナスの場合は0が最良です。これらの相違点の最大値を把握する必要があります。最後に、前記最大値が所望の結果である。

これは基本的にアルゴリズムの機能です。明確な実装がrunning here

#include <stdio.h> 
#include <limits.h> 

int main(void) 
{ 
    int A[8]={10,23,6,12,4,1,0,3}; 
    int i,min_i, profit_i, best_profit=0,n=8; 

    min_i=A[0]; 
    for(i=1;i<n;i++) 
    { 
     profit_i = A[i] - min_i; 
     best_profit = (profit_i > best_profit) ? profit_i : best_profit; 

     if(A[i]<min_i) 
     { 
      min_i=A[i]; 
     } 

    } 

    printf("Best profit: %d", best_profit); 
    return 0; 
} 

見つけることができ、不要なローカル変数がありますが、私は、彼らが見て、ロジックが容易になりました。