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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #149: Searching for a maximum-sum subsequence.
You are viewing a single comment's thread. Return to all 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.