Максимизировать прибыль от акций (максимальный субарах)

Question

Я читаю «Введение в алгоритмы». В проблеме максимального субарама (глава 4) автор утверждает, что максимальная прибыль от покупки и продажи доли не может быть рассчитана просто путем нахождения максимума и минимума массива. Автор говорит об альтернативах, таких как грубая сила, вычисляя все возможные комбинации дат покупки и продажи, для которых требуется 0 (n^2) времени. Другой альтернативой было бы найти максимальный субаракр ежедневных изменений в ценовом массиве.

Однако я закодировал алгоритм, который займет 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

Здесь ваши ищут максимальную выгоду вы можете сделать через покупку и продажу stock один раз (один раз важно).

Ваш алгоритм делает предположение, что лучшая прибыль будет получена из самой низкой цены исполнения запаса. Это неправильно: например, с 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}. В конце концов, необходимая прибыль - это сумма максимального подмассива.

Другой способ взглянуть на это - итеративно сохранить вкладку минимума массива 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; 
} 

Есть ненужные локальные переменные, но я обнаружил, что они сделали логика легче увидеть.