# Project Euler 149 – Maximum-sum Subsequence

#### Posted on January 16, 2014

##### Last updated on January 16, 2014

Solution to Project Euler problem 149.

What we have is an $$N \times N$$ grid and we need to find the maximum-sum subsequence (contiguous) along any vertical, horizontal, diagonal or anti-diagonal line. First, think about the 1D case where we simply have an array and need to find the maximum-sum contiguous subarray. This is solved via Kadane’s algorithm. The algorithm is as follows:

Now, we simply need to run Kadane’s algorithm on all horizontal, vertical, diagonal and antidiagonal strips. Below is the Java code that produces the correct answer. It probably should be refactored to look a bit better, but this version below still works.

Markdown SHA1: 6830bccb9dc2294001ae79c5c04ef744ec871419