Maximise the profit of shares (Maximum subarray)

Question

I am reading "Introduction To Algorithms". In the maximum subarray problem (Chapter 4), the author claims that the maximum profit of buying and selling a share cannot be calculated just by finding the maximum and minimum of the array. The author speaks of the alternatives such as brute force by calculating all possible combinations of buy and sell dates which would require 0(n^2) time. The other alternative would be to find the maximum subarray of daily-changes in price array.

However, I coded an algorithm which would take 0(n) time and find the maximum profit. This is in 0(n) vs maximum subarray problem of 0(n log n). But I know the authors cannot be wrong. Where am I going wrong ? Is my algorithm correct?

#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;
}

As given in GeeksForGeeks (http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/), the input for daily change in stock prices are A[ ]={-2, -5, 6, -2, -3, 1, 5, -6}. I have taken base price as 10 and have run the algorithm as A[ ]={10,8,3,9,7,4,5,10,4};

Input : 10,8,3,9,7,4,5,10,4

Output: 7

As you say, a solution is given by the maximum sequence problem. But the maximum sequence problem is solved in O(n) space and O(1) time. Where (what page) does it say O(n log n)? — Lawrence Wu
Your algorithm seems to have the right idea. But I think you should take out prevmax and instead do if (max-min > currmax) currmax = max-min; and just print currmax as your answer. Otherwise you will be incorrect if the answer comes before prevmax. Also you should initialize currmax to 0 in case there are no profits to be made. — Lawrence Wu
@LawrenceWu : Page 74, CLRS 3E. It says 0(n lg n). Yeah, prevmax was not needed. — sagar_jeevan
@AbhishekBansal: The output was still 7. However I changed the input now. — sagar_jeevan
Read the last sentence, it says that divide and conquer is not the best but O(n) is achievable, which is what you've done essentially. "As Exercise 4.1-5 shows, there is in fact a linear-time algorithm [...]" — Lawrence Wu

Rerito Rerito · Accepted Answer · 2016-07-12T07:14:55

Here your are looking for the maximum benefit you can make through buying and selling a stock once (the once is important).

Your algorithm makes the assumption that the best profit will arise from the lowest strike price of the stock. This is wrong: for example with A[] = {10,23,6,12,4,1,0,3}, your program outputs 3 whereas the maximum benefit is obviously 13 (proof on Coliru)

A characterization of the optimal benefit is to compute the delta array of the stock fixings (the A[ ]={-2, -5, 6, -2, -3, 1, 5, -6} array you quoted), then get the maximum subarray. With my example we get F[] = {13, -17, 6, -8, -3, -1, 3} and the maximum subarray is {13}. In the end, the required profit is the sum of the maximum subarray.

Another way to look at it is to iteratively keep tab of the minimum of the array A[0..i-1] (i ranging from 1 to n-1). At index i (ie selling at time i), the best profit is the difference A[i] - min(A[0..i-1]), or 0 if that difference is negative. You now have to keep track of the maximum of these differences. In the end, the said maximum is the desired result.

This is basically what your algorithm does. A clearer implementation can be found 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;
}

There are unnecessary local variables but I found they made the logic easier to see.

Maximise the profit of shares (Maximum subarray)

1 Answers