Problem 663
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.

 Posts: 3
 Joined: Tue Apr 02, 2019 4:51 pm
Problem 663
Hello everyone!
I'm quite new to the site, and I really need a clarification about this one. It's written:
"After each step i, define Mn(i) to be max{∑j=pqAn[j]:0≤p≤q<n}, the maximal sum of any subsequence of An."
I'm not sure I fully understand what is meant by subsequence, as the example is a bit misleading. Is it simply an ordered subset of An with the order induced by An (like the mathematical definition of subsequence would suggest) or does it also have the property to contain all numbers between p and q (like the sigma notation would indicate) ? I've been trying to figure it out by myself, but I had no luck so far, so if you please could help me here I'd be very grateful!
I'm quite new to the site, and I really need a clarification about this one. It's written:
"After each step i, define Mn(i) to be max{∑j=pqAn[j]:0≤p≤q<n}, the maximal sum of any subsequence of An."
I'm not sure I fully understand what is meant by subsequence, as the example is a bit misleading. Is it simply an ordered subset of An with the order induced by An (like the mathematical definition of subsequence would suggest) or does it also have the property to contain all numbers between p and q (like the sigma notation would indicate) ? I've been trying to figure it out by myself, but I had no luck so far, so if you please could help me here I'd be very grateful!
Re: Problem 663
From Wikipedia:
"In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements'
See: https://en.wikipedia.org/wiki/Subsequence
"In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements'
See: https://en.wikipedia.org/wiki/Subsequence

 Posts: 3
 Joined: Tue Apr 02, 2019 4:51 pm
Re: Problem 663
Thanks a lot! I knew the definition, I just wanted to make sure.
Re: Problem 663
I am sorry, michelebastione, in this problem we we did NOT use the word subsequence according to the wikipedia's definition, but the way it's described in the definition of $M_n(i)$ (as this would also make the problem quite trivial, since you'd only have to add all positive values of the sequence. Unfortuneately the example also doesn't clarfify this by itself).
So according to our definition the maximal subsequence of $1,2,3,4,5$ is $3+4=7$ and not $1+3+4=8$
We could make this clearer by adding something like "subsequences of $A_n$, that are made up of consecutive elements."
I'll discuss this with the dev team shortly.
So according to our definition the maximal subsequence of $1,2,3,4,5$ is $3+4=7$ and not $1+3+4=8$
We could make this clearer by adding something like "subsequences of $A_n$, that are made up of consecutive elements."
I'll discuss this with the dev team shortly.
Re: Problem 663
We've edited the problem text (inserted "contiguous"). Thanks, michelebastione, for mentioning this issue.

 Posts: 3
 Joined: Tue Apr 02, 2019 4:51 pm
Re: Problem 663
Thank you very much!
I must admit I was very puzzled, I was having quite a hard time trying to figure out what I was missing. Now it's much more cleare to me, and I'm going to get to work asap to see if everything checks out!
I must admit I was very puzzled, I was having quite a hard time trying to figure out what I was missing. Now it's much more cleare to me, and I'm going to get to work asap to see if everything checks out!
Re: Problem 663
Just wanted to check, say the array $A_n = [8, 1, 2, 3, 5, 6, 100, 2, 4, 6]$, so would the maximum subarray sum be $8 + ( 1) + 2 + 3 + ( 5) + 6 = 13$. So if negative values can be "absorbed", we should "absorb" them?
my friend key > 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L
Re: Problem 663
That's what the definition of M implies, and you won't get the right value for S(107, 1000) without it. So, yes. A maximal sum can include negatives (as long as the positives on the other side are worth it).

 Posts: 2
 Joined: Sat Apr 13, 2019 11:40 am
Re: Problem 663
My python code find S(5,100)=2416, S(14,100)=3881 and S(107,1000)=1618572.
But when I started to find S(10000003,10000000) it's say than I need 1 year to calculate results.
1 M= XXX Iteration time: 5.44500
2 M= XXX Iteration time: 5.89250
3 M= XXX Iteration time: 5.29500
So 10000000 iterations will be calculated near 1 years.
So we need some tricks to calculate M but not just stupid "maximal sum of any contiguous subarray"?
But when I started to find S(10000003,10000000) it's say than I need 1 year to calculate results.
1 M= XXX Iteration time: 5.44500
2 M= XXX Iteration time: 5.89250
3 M= XXX Iteration time: 5.29500
So 10000000 iterations will be calculated near 1 years.
So we need some tricks to calculate M but not just stupid "maximal sum of any contiguous subarray"?
Re: Problem 663
I think so, that is exactly why I have not been able to solve this problem. I was unable to come up with a "dynamic" version of the "maximum subarray sum" algorithm. :
my friend key > 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L

 Posts: 2
 Joined: Sat Apr 13, 2019 11:40 am
Re: Problem 663
In my case I use "dynamic" version of the "maximum subarray sum" algorithm but in Python.
For array size = 10000003 it take 5.4 sec to find "maximum subarray sum" M for every steps .
So I think we need to find some algorithm to skip duplicate results, i.e. when for example M32=M33=M34=M35=M36.
Re: Problem 663
This board is not meant to discuss solutions.
As made clear from the onset it is meant to resolve problems with understanding what is asked.
As far as I can see both of you understand perfectly what is asked.
Attemps to discuss things further will be deleted.
As made clear from the onset it is meant to resolve problems with understanding what is asked.
As far as I can see both of you understand perfectly what is asked.
Attemps to discuss things further will be deleted.