Project Euler Forum

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!

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

Thanks a lot! I knew the definition, I just wanted to make sure.

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.

We've edited the problem text (inserted "contiguous"). Thanks, michelebastione, for mentioning this issue.

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!

<deleted post>

vamsikal3 wrote: Fri Apr 05, 2019 12:35 pm Just wanted to check, say the array $A_n = [8, -1, 2, 3, -5, 6, -100, 2, 4, 6]$, so would the maximum sub-array sum be $8 + (- 1) + 2 + 3 + (- 5) + 6 = 13$. So if negative values can be "absorbed", we should "absorb" them?

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).

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"?

<deleted post>

vamsikal3 wrote: Sat Apr 13, 2019 1:10 pm 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 sub-array sum" algorithm. :

In my case I use "dynamic" version of the "maximum sub-array sum" algorithm but in Python.
For array size = 10000003 it take 5.4 sec to find "maximum sub-array 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.

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.