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.
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.
for 8th i am getting 397 instead of 430 plz check my algo is correct cuz its giving all other answer as correct
Can anyone explain how the 7th answer is 334?....coz i am getting 330 in the first column. Thanks.