Project Euler #149: Searching for a maximum-sum subsequence.

Sort by

recency

|

4 Discussions

|

  • + 0 comments

    This is very tricky problem as we need to devise algorithm with O(n^2) time complexity. For rows, columns and diagonals it's relatively simple. The real challange here is to devise algorithm for antidiagonals. To build next square I add add bottom row and right column. For antidiagonals it means interchangeably prepending and appending element. For antidiagonals I keep track of the range of maximum subsequence, max sum of subsequence, maximum consecutive sum and its range, minimum consecutive sum and its position and finally sum of sequence preceding max subsequence.

  • + 2 comments

    First, I would like state that my code is C# not Python. I am at 50 points on the first half of the test cases. I take approximately my whole alloted time of 3 seconds for most of the test cases. Three seconds sounds like a pretty tight time constraint for C#. I am using Kadane's algorithm which is Order(n) where n is the length of the array to be searched for a maximum sum. I could perhaps use parallel tasks to speed things up in some cases. I will complete, if possible. the Project Euler Problem 149 with this code, and report my runtime in this forum. Thanks in advance for any useful advice.

    • + 1 comment

      Here is the output from my test using the ProjectEuler Problem 149. I got the problem correct but I took the spoiler out of the following output:

      -393027 86613

      time in milliseconds = 243 Press any key to continue . . .

      The first two numbers are a check of the lagged Fibonacci generator namely s[10] and s[100]. The blank line is where the correct output was taken from the output display.

      • + 0 comments

        The code for the ProjectEuler Problem 149 seems to scale well. Here are my results for n = 5000 instead of 2000. Could someone check the number before the time in milliseconds?

        -393027 86613 89385246 time in milliseconds = 1609 Press any key to continue . . .

    • + 0 comments

      Time is measured as processor time. Parallelization will not help you.

  • + 1 comment

    for 8th i am getting 397 instead of 430 plz check my algo is correct cuz its giving all other answer as correct

    • + 0 comments

      It sounds like maybe your algorithm isn't checking all sums that start in the last column and extend downward + toward the left.

  • + 1 comment

    Can anyone explain how the 7th answer is 334?....coz i am getting 330 in the first column. Thanks.

    • + 2 comments

      The reverse diagonal from (7,2) to (4,5) has value 334.

      • + 0 comments

        got it. thanks a lot :)

      • + 1 comment

        I am using the second version of the Kadane algorithm given in a Wikipedia article implemented in C# instead of Python. For the example input case with n = 7, I get a maximum row sum of 330, a maximum column sum of 270, and a maximum diagonal sum of 60, and a maximum anti-diagonal sum of 135. That means the maximum sum should probably be 330 also like n = 6. I get the author's results for n = 1 to 6 and 8 but I disagree with n = 7. Who is right? I suspect the fault is my implementation of the Kadane algorithm. https://en.wikipedia.org/wiki/Maximum_subarray_problem

        • + 1 comment

          Hi James...the reverse diagonal from the (7,2) position to (4,5) has value 334. It is not part of any of the subsquares until n=7.

No more comments