## Problem 663

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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.

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 post any spoilers
michelebastione
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!

hk
Posts: 10871
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### 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

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

Animus
Posts: 1903
Joined: Sat Aug 16, 2014 1:23 pm

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

Animus
Posts: 1903
Joined: Sat Aug 16, 2014 1:23 pm

### Re: Problem 663

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

michelebastione
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!

vamsikal3
Posts: 113
Joined: Sat Oct 01, 2016 9:25 am

### 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 sub-array 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

DJohn
Posts: 63
Joined: Sat Oct 11, 2008 12:24 pm

### Re: Problem 663

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

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

vamsikal3
Posts: 113
Joined: Sat Oct 01, 2016 9:25 am

### 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 sub-array sum" algorithm. :
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L

MaksymTatarenko
Posts: 2
Joined: Sat Apr 13, 2019 11:40 am

### Re: Problem 663

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.

hk