rbrt.coleman
BAN USER
This problem is similar to some other dynamic programming problems, all of which are looking for the largest cumulative sum sub-array. In this case, we're not looking for the largest cumulative sum, but the most positive a[right_idx] - a[left_idx].
General solution:
The crux of the solution is to keep a left pointer, and run right pointers forward, cumulatively summing the elements as we go. If our cumulative sum is larger than any we've found so far, we replace that best result with the new one. We stop each of these cumulative runs when the cumulative sum drops to zero. When the cumulative sum drops to zero, we move the left pointer to the location of the right pointer and begin another forward run with the right pointer.
We stop the whole process when the right pointer reaches the end.
Specific solution:
In this case, we don't compute a cumulative sum, but the a[right_idx] - a[left_idx].
The complexity will be O(n) in compute, since for each new run, we move the left pointer to meet the right pointer. Memory use will be O(1) in memory since the only auxiliary data structures we need are pointers and the best difference.
def buy_low_sell_high(stock_trace):
best_diff = 0
best_left = -1
best_right = -1
left_idx = 0
right_idx = 0
while right_idx < len(stock_trace) - 1:
right_idx = left_idx + 1
# run, right pointer
while right_idx < len(stock_trace) - 1:
diff = stock_trace[right_idx] - stock_trace[left_idx]
if diff > best_diff:
best_diff = diff
best_left = left_idx
best_right = right_idx
elif diff <= 0:
# move left pointer to right pointers location
left_idx = right_idx
# start a new run
break
right_idx += 1
print("best return: {}".format(best_diff))
print("buy at (val, idx): ({},{})".format(stock_trace[best_left], best_left))
print("sell at (val, idx): ({},{})".format(stock_trace[best_right], best_right))
Some inputs
stock_trace1 = [
0.010813118732461158,
7.848782642974635,
6.412165671008653,
2.41400198901051,
7.380876605993766,
7.050665938613819,
1.545930172530945,
4.890855121484591,
4.007390799132676,
4.959796684292704,
8.252891965307231,
1.2789829911948636,
3.0432514514857867,
6.694507808651309,
9.400862760505838,
0.5439483796581279,
5.538854666259302,
0.15483879273656131,
5.923645176042162,
1.6929368892019125
]
stock_trace2 = [
7.848782642974635,
6.412165671008653,
2.41400198901051,
7.380876605993766,
7.050665938613819,
1.545930172530945,
4.890855121484591,
4.007390799132676,
4.959796684292704,
8.252891965307231,
0.010813118732461158,
1.2789829911948636,
3.0432514514857867,
6.694507808651309,
9.400862760505838,
0.5439483796581279,
5.538854666259302,
0.15483879273656131,
5.923645176042162,
1.6929368892019125
]
stock_trace3 = [
7.848782642974635,
6.412165671008653,
2.41400198901051,
7.380876605993766,
7.050665938613819,
1.545930172530945,
4.890855121484591,
4.007390799132676,
4.959796684292704,
8.252891965307231,
1.2789829911948636,
3.0432514514857867,
6.694507808651309,
9.400862760505838,
0.5439483796581279,
5.538854666259302,
0.010813118732461158,
0.15483879273656131,
5.923645176042162,
1.6929368892019125
]
The outputs
print("Stock Trace 1")
buy_low_sell_high(stock_trace1)
print("Stock Trace 2")
buy_low_sell_high(stock_trace2)
print("Stock Trace 3")
buy_low_sell_high(stock_trace3)
Stock Trace 1
best return: 9.390049641773377
buy at (val, idx): (0.010813118732461158,0)
sell at (val, idx): (9.400862760505838,14)
Stock Trace 2
best return: 9.390049641773377
buy at (val, idx): (0.010813118732461158,10)
sell at (val, idx): (9.400862760505838,14)
Stock Trace 3
best return: 8.121879769310974
buy at (val, idx): (1.2789829911948636,10)
sell at (val, idx): (9.400862760505838,13)
We can do this in O(n) with O(1), constant, memory using the original array, by swapping elements.
We need two pointers, one starting at index zero (the right index), and one starting at n-1 (the right index).
We test each element at a[left_idx] to see if it's zero.
If it equal to zero, we swap it with the element at a[right_idx], or the element at the left size of the last zero we moved to the end. Since we put a zero at that index, we have to decrement right_idx.
If that element at the left_idx is not zero, we increment the right pointer.
We stop when the two pointers are at the same location.
def move_zeros_to_end(a):
n = len(a)
right_idx = n - 1
left_idx = 0
while left_idx < right_idx:
if a[left_idx] == 0:
a[left_idx], a[right_idx] = a[right_idx], a[left_idx]
right_idx -= 1
else:
left_idx += 1
return a
Reppepsyfarely, Front-end Software Engineer at 247quickbookshelp
I am Pepsy , a security supervisor at Edge Services for the last 4 years managing security teams and corporate environments ...
RepAriaScott, abc at 247quickbookshelp
I am a qualified medical representative who has been in the industry for many years and has proven sales experience ...
Reprizzafilher, Java Developer at Achieve Internet
Sorter with 3+ years of experience , performs duties in a safe manner in compliance with all local, state, and federal ...
RepDavidRNichols, Analyst at AMD
Skilled communicator and listener with a knack for remedying conflict, and keen organizational skills which allow for effective delivery of ...
RepAayshaRosie, HTML Freshers at Abs india pvt. ltd.
Aaysha , a book editor with 4 years of experience with increasing readership and developing skilled writers. At the Daily Record ...
Repjoyceclark, Graphics Programmer at Denmin Group
I am Joyce, a highly talented and passionate writer expert in storytelling. Outside of my writing profession, I’ve hobbies ...
RepLisaNoto, Android Engineer at ADP
Annie has nearly 10 years of experience working on anadromous and estuarine fishery issues in California. She serves as a ...
Repamandaben422, Graphics Programmer at Abs india pvt. ltd.
Hi, I am a webmaster from the USA. I think social networks have the power to connect two different people ...
RepDaisyRoss, Video game designer at A9
Seeking lead game programmer and position to utilize knowledge and skills to advance portfolio and potential for increased responsibility. Explore ...
RepSharonSwann, AT&T Customer service email at A9
Bilingual, self-motivated Air Hostess with a proven record of providing excellent customer service and exceeding all corporate and personal expectations ...
RepKianaEmmert, SDE1 at Home Depot
I am Kiana , an Entertainment Journalist, having 5 years of experience, in my career I have covered a lot of ...
RepMoniKim, Animator at Clean Power Research
I am Moni , a reliable Special Projects/Order Filler people oriented personality with great organizational and interpersonal communication skills. I ...
RepJoseElkins, Animator at ASU
I am working as Human Resources Associates, and my duties are for obtaining, recording, and interpreting human resources information within ...
Repthelmasaraht, Applications Developer at Accolite software
A child protection social worker is responsible for a variety of services designed to help families and children in a ...
Repdanikademers, HTML Experienced at Barclays Capital
I am Danika , working as a junior content writer with Jafco where I use my blog writing and social media ...
Repandrealmoore45, Analyst at 247quickbookshelp
My name is Andrea and I Live in california. I like to read articles from some interesting topics.And today ...
RepMiaMiller, abc at A9
Experienced software engineer with a passion for developing innovative programs that expedite the efficiency and effectiveness of organizational success. Well-versed ...
Rephoychrista, Blockchain Developer at ASU
Worked with Clients to guide them through the event details about copier leasing companies and served as their personal coordinator ...
Repkrishamoris, Area Sales Manager at Accolite software
I am Krisha , an organized Cosmetology Instructor with 4 years of experience. Successful at keeping detailed records and personalizing lesson ...
Repkany7635, optician at AMMB
I am a detail oriented and knowledgeable optical assistant with 2 years of experience in an optometry office setting. Collect ...
Repjudithasmith175, Accountant at Akamai
Hey, my name is Terry and I completed all my study from California. And Nowadays I am working as a ...
Repbungayasorya, Accountant at BrowserStack
An archeologist is an expert on history who gains expertise through experience with historical documents and artifacts. The archaeological record ...
RepBriannaWright, Analyst at A9
I am a skilled project manager with years of exemplary service in diverse IT roles. I am passionate about utilizing ...
RepNoraMiller, abc at A9
Confident and dedicated photographer with experience in both professional and freelance photography.. Prioritizes communication on the job to avoid errors ...
RepYolandaDial, Conciliator at Custom Lawn Service
I have excellent communication and negotiation skills, enabling me to actively listen to each party's grievances, concerns, and interests ...
RepAakeshCruz, Accountant at Tinder
Exceptional knowledge of mathematical concepts, accounting and finance topics, tax code, and banking principles.Worked with clients and CFOs to ...
A bidirectional BFS, maintaining the a hash table of explored nodes for each and the hops to get to that node. Whenever the frontier node of either BFS touches a node that is in the explored set of explored nodes for the other, the total hops is the sum of from each BFS to the connecting node.
- rbrt.coleman October 05, 2016