We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
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.
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.
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 . . .
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
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.
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.
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.
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 . . .
Time is measured as processor time. Parallelization will not help you.
for 8th i am getting 397 instead of 430 plz check my algo is correct cuz its giving all other answer as correct
It sounds like maybe your algorithm isn't checking all sums that start in the last column and extend downward + toward the left.
Can anyone explain how the 7th answer is 334?....coz i am getting 330 in the first column. Thanks.
The reverse diagonal from (7,2) to (4,5) has value 334.
got it. thanks a lot :)
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
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.