₦airaland Forum

This space reserved...will post in a bit

I got this problem this morning...companies seem to like asking DP problems for some reason.

Here it goes:

You are a stock broker. You have a list of gains/losses for N days for some stock. For example, if N=7 and corresponds to one week (Monday through Sunday), the gain/losses might look like the following:

-1 10 5 -3 7 0 0

So the stock went down by 1 dollar on Monday, up by 10 on Tuesday,, up by 5 on Weds, etc.

You are interested in computing the smallest profit over any consecutive sequence of days.

For example, if N=365, there might have been a really bad sequence of say 3 consecutive days when the stock fell really hard. For this to be the worst consecutive sequence, the amount of money accrued on that day obviously has to be worse than that of any other sequence. So in particular, I lose more money on this particular 3 day sequence than I lost on
any other:

1 day sequence
2 day sequence
3 day sequence
4 day sequence..
etc.


Eyeballing the above 7 day sequence, the worst profit seems to -3.

Your job is to write an algorithm that computes this smallest profit. Note that you don't need to necessarily identify the starting and end days associated with the smallest profit, just the number itself.

Hints:
1) There exists a DP-based algorithm that runs in O(N) time.
2) First think perhaps of a brute-force solution, the one someone might do if they've never heard of dynamic programming before in their lives. I came up with a brute force solution that is O(N^3). Then think if you can use DP to come up with a better solution.

Here is the crappy solution that doesn't use DP.

Essentially, assuming we have a list of N numbers, we need to
1) examine all possible pairs of indices a,b for which a<b
2) Compute the profit/loss over the interval a through b
3) return the smallest profit over all of the (a,b) pairs we found in step (1).

So, for step 1, how many pairs are there? Just T=(N^2-N)/2 (it is easiest to see this by drawing a picture).

For each interval, we can compute its profit/loss in at most time N.

Taking the maximum over the T intervals takes at most another O(T) time.

So overall, we have a O(N^3) algorithm. Would be pretty straightforward to code up.

Here is python code for the slow algorithm:
http://pastebin.com/6yyXJQXh

And here is the result of running the above code on some examples:
-------------------------------------
[ -7 -2 7 -8 0 6 7 -9 -2 3 -7 4 -10 2 -4]
Our worst profit is: -23
Starting/ending indices of worst profit is: (7, 14)
[-9 -9 -7 6 -8 6 -7 -5 2 -6 0 -2 5 4 -5]
Our worst profit is: -39
Starting/ending indices of worst profit is: (0, 11)
[-9 -2 4 -3 9 -6 -1 -2 -3 6 -3 -8 6 -9 -9]
Our worst profit is: -30
Starting/ending indices of worst profit is: (0, 14)
[ 3 7 -7 -3 -1 -8 -2 -6 6 -7 1 -6 -5 1 3]
Our worst profit is: -38
Starting/ending indices of worst profit is: (2, 12)
[ 6 -1 -3 -4 1 -2 9 0 9 3 4 7 8 -8 -3]
Our worst profit is: -11
Starting/ending indices of worst profit is: (13, 14)
------------

ekt_bear: And here is the result of running the above code on some examples:
-------------------------------------
[ -7 -2 7 -8 0 6 7 -9 -2 3 -7 4 -10 2 -4]
Our worst profit is: -23
Starting/ending indices of worst profit is: (7, 14)
[-9 -9 -7 6 -8 6 -7 -5 2 -6 0 -2 5 4 -5]
Our worst profit is: -39
Starting/ending indices of worst profit is: (0, 11)
[-9 -2 4 -3 9 -6 -1 -2 -3 6 -3 -8 6 -9 -9]
Our worst profit is: -30
Starting/ending indices of worst profit is: (0, 14)
[ 3 7 -7 -3 -1 -8 -2 -6 6 -7 1 -6 -5 1 3]
Our worst profit is: -38
Starting/ending indices of worst profit is: (2, 12)
[ 6 -1 -3 -4 1 -2 9 0 9 3 4 7 8 -8 -3]
Our worst profit is: -11
Starting/ending indices of worst profit is: (13, 14)
------------

Based on ur examples above, I now understand wht is required...lol english is simple....I would try It out once I get to my pc

---

http://pastebin.com/076mpn2k

---

my implementation

How does your code work on sample inputs? Did you try it on the same sample inputs I posted? If so, does it correctly identify the least profit interval?

Yea it works....I tried it on ur samples....it recieves all d values in a single line (each seperated by a space) and prints out d GMP(greatest minimum profit)

Why did you use "numpy"??
You should have implemented it using the standard modules that comes with python.... Numpy wasnt exactly necessary here.

₱®ÌИСΞ:
Yea it works....I tried it on ur samples....it recieves all d values in a single line (each seperated by a space) and prints out d GMP(greatest minimum profit)

OK, it looks like your approach works on the examples I tried. Good job. It wasn't what I had in mind, but that is fine. Can you modify your code to return the correct indices too, corresponding to the least profitable interval?

WhiZTiM: Why did you use "numpy"??
You should have implemented it using the standard modules that comes with python.... Numpy wasnt exactly necessary here.

This doesn't really matter. If you like, modify the example to only use the library random rather than np.random.

Here is my own solution: http://pastebin.com/6yyXJQXh

Mine basically computes the worst list starting at each value i=1,2,...,N, then takes the minimum over those N different possible choices.
I do this by first computing a solution for i=N, then i=N-1, etc.

I think Prince's solution is similar to mine, except:
a) computes answers from the front to the beginning (i.e., from i=1, then i=2, etc)
b) and then rather than taking the minimum at the very end, just computes a running version of it.

(b) in particular means he uses less memory than I do.

@ekt_bear and @prince can i see a java implementation of your code?

@ekt_bear @javanian ok...on it

@ekt_bear

---

http://pastebin.com/hhUbq4xb

---

@javanian

---

http://pastebin.com/5s4Mpw5k

---

sori 4 d delay...been quite busy

Yep, so yours is a DP algorithm, running forwards

ekt_bear: Yep, so yours is a DP algorithm, running forwards

Yea...I have done such in d past, tho it ws for maximum sub array.....still d same algorithm ( Kadane's Algorithm ) just a few changes... runtime still O(n)

Ah, interesting. Yeah, max subarray is equivalent to this problem (max subarray of the list L is the min subarray of the list M with M[i]=-L[i]).

Thanks @prince

@ekt_bear yea... Spot on.. @javanian yw

What a wonderful discussion. For a while I have been trying to understand dynamic programming, I'm really struggling with it. I have gone online and seen tutorials but I still don't understand the concept behind most answers and some it take me hours to understand. Please I want to know if someone here knows a superb material for absolute beginners to understand dynamic programming

Nmeri17:
The best way to learn it IMO is by practising. If you've gotten a solid grasp of data structures, you can use a piece of paper and a pen to strategize how to achieve your aim-- be it meta programming or plain dynamic programming. Tutorials will only serve to confuse you.

Shortly after I acquainted myself with it, I came across this tutorial. Most, if not all, of what is discussed there is correct but is convoluted and ambiguous. With some concentration, the concept itself is simple. If I'd read it first, I'll be confused and frustrated. My advice is don't look for who'll teach you. You can figure it out yourself.

Thanks. I'm grateful for this