How would approach this problem

[foodwoods52]

INPUT: A list of daily wheat prices per bushel, one per day.

OUTPUT: The maximum profit (per bushel) that could have been achieved by buying and selling on different days.

Example:

Input: [ 3, 4, 9, 4, 4, 6 ]
Output: 6
(Reasoning: Buy on day 1 at $3, sell on day 3 at $9 for a $6/bushel profit)

[MikeStgt]

#include <iostream>
using namespace std;

int main()
{
    unsigned i(0), min(0), max(0), dwpb;
    cout << "Enter wheat prices per bushel of six consecutive days: ";
    min -= 1;
    do
    {
        cin >> dwpb;        // dayly wheat price per bushel
        
        if (dwpb > max)
        {
            max = dwpb;
            if (min > dwpb) min = dwpb;
        }
    } while (++i < 6);
    cout << "\nmax profit was: (max-min) " << max - min << " as max=" << max << " and previous min=" << min;
}

Tested only with your example.

Edit: replaced for() loop by do..while

[jonnin]

no offense but needs work

Enter wheat prices per bushel of six consecutive days: 10
1
2
3
4
4

max profit was: (max-min) 0 as max=10 and previous min=10 

also I think you can't take absolutes. it ordered, so 10 followed by 1 .. you can't time travel, can you?

#include <iostream>
using namespace std;
int main()
{
  int  input[] = { 5,5,4,6,5,5};
  int j = 0;
  int k = 5;
  int mx = input[5]; 
  int mn = input[0];
  do
{
   if( input[k] >= mx)
      mx = input[k--];
   else
   if(input[j] <= mn)
     mn=input[j++];
    else {j++; k--;}
} while( j<=k);
cout<< mx << " " << mn << endl;
}

ok maybe it works now. seems to for a few test cases. current test case does not work, but the code is close and gives you an idea of what the answer might look like.

which does not answer the problem.. how do you approach it?
being pretty solid with the language I coded first and messed with it to debug it, which is terrible for a serious problem. What you should do is solve it on paper for several conditions... what if day 1 most expensive and day 2 is cheapest, what is the answer? Your default test, of course. And so on. After doing that, ask what you need... you need an array of values, a way to iterate it, and a way to track your best answer so far, and an algorithm to improve your answer as you iterate the array. All but the algorithm translate into variables which you see in the code. The algorithm.. well, I decided (hopefully its correct) that I needed to start on the ends of the array and work towards the middle until the tracking variables crossed each other, looking at each step for an improvement, and if no improvement is found, move on toward the center.

[MikeStgt]

you can't time travel, can you?

You could trade options, wagers on future.

Well, I knew my suggested process is faulty, so my restriction: Tested only with your example.

[ne555]

> you can't time travel, can you?
you could before https://www.youtube.com/watch?v=RLySXTIBS3c
https://en.wikipedia.org/wiki/Naked_short_selling

> (Reasoning: Buy on day 1 at $3, sell on day 3 at $9 for a $6/bushel profit)
¿cant buy again on day 4 and sell on day 6, for extra $2 and a total of $8?

[jonnin]

heh. Mine still has at least one bug, so don't take my comment to heart.
Ive hacked on it a bit more.
Anyone see any cases it still can't do?
missed the double move problems... (both conditions failed else increment both) which ended (originally) ignoring some candidates. Fixed that and the loop condition to force it to check one last time (last element ignored problem).

Which reiterates what I said in the explain... coding first and fixing after isn't exactly the best practice …

Ness, if you want to figure out the logic to buy and sell multiple times in the window, be my guest :) That looks like more work than I have in me today.

[MikeStgt]

Anyone see any cases it still can't do?

Yes, how about the example from OP? Input {3, 4, 9, 4, 4, 6}, output: 6 3 (mx and mn) :(
And what about the valuable hint from ne555? (Thank you for the two links BTW, I knew about short selling, but naked short selling is new to me.)

[jonnin]

its going to be one of those days... it was working for that, and I broke it fixing the other cases.

[MikeStgt]

#include <iostream>
using namespace std;

int main()
{
    unsigned i(1), min, max, dwpb;
    cout << "Enter wheat prices per bushel of six consecutive days: ";
    cin >> max;        // first day .. run in cycle
    min = max;
    do
    {
        cin >> dwpb;        // dayly wheat price per bushel (day 2..6)
        
        if (dwpb < max)
        {
            if (max > min)
                cout << "\nProfit opportunity: " << max - min << " with max=" << max << " and previous min=" << min;
            min = dwpb;
        }
        max = dwpb;
    } while (++i < 6);
    if (max > min)
        cout << "\nProfit opportunity: " << max - min << " with max=" << max << " and previous min=" << min;
    cout << "\nDone with this week.";
}

Start of the week is a "run-in cycle", for a price drop see if there was an opportunity and do another "run-in cycle" within the week. Now, to be in compliance with the OP, you should eliminate the lesser profitable chances. To respect the profit taking hint of ne555 I leave it as is.

[MikeStgt]

@ne555
Thank you once more for the link to Eddie Murphy's 'Trading Places' clip. What a wonderful persiflage. Reminds me a discuss once with a colleague, who argued you could make or waste money at the stock exchange. Sure, if you are a gambler within the game. Regarding it from the outside (larger set system boundaries) I am with Lavoisier: "Nihil ad nihilo, nihilo ad nihil."

Sorry for the subject drift.