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:
int maxContiguousSubsequence(int[] a){
int maxSoFar = 0;
int maxEndingHere = 0;
for(int i = 0; i < a.length; i++){
maxEndingHere = Math.max(maxEndingHere + A[i], 0);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}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.
long solution(){
long[][] M = new long[2000][2000];
long[] S = new long[2000*2000+1];
long iter = 1;
int mod = 1000000;
for(int i = 0; i < 2000; i++){
for(int j = 0; j < 2000; j++){
long elem = 0;
if(iter <= 55){
elem = ((100003-200003*iter+300007*iter*iter*iter)%mod+mod)%mod - 500000;
}
else{
elem = ((S[(int)iter-24] + S[(int)iter-55] + 1000000)%mod+mod)%mod - 500000;
}
S[(int)iter] = elem;
M[i][j] = elem;
iter++;
}
}
long max = Long.MIN_VALUE;
int N = 2000;
// max over rows
for(int i = 0; i < N; i++){
long maxSoFar = 0;
long maxEndingHere = 0;
for(long elem : M[i]){
maxEndingHere = Math.max(maxEndingHere+elem,0);
maxSoFar = Math.max(maxSoFar,maxEndingHere);
}
max = Math.max(max,maxSoFar);
}
// max over columns
for(int i = 0; i < N; i++){
long maxSoFar = 0;
long maxEndingHere = 0;
for(int j = 0; j < N; j++){
maxEndingHere = Math.max(maxEndingHere+M[j][i],0);
maxSoFar = Math.max(maxSoFar,maxEndingHere);
}
max = Math.max(max,maxSoFar);
}
// max over diagonals
for(int i = 0; i < N; i++){
long maxSoFar = 0;
long maxEndingHere = 0;
int row = i;
int col = 0;
for(int j = 0; j <= i; j++){
maxEndingHere = Math.max(maxEndingHere+M[row][col],0);
maxSoFar = Math.max(maxSoFar,maxEndingHere);
row--;
col++;
}
max = Math.max(max,maxSoFar);
}
// max over diagonals 2
for(int i = 0; i < N; i++){
long maxSoFar = 0;
long maxEndingHere = 0;
int row = N-1;
int col = i;
for(int j = 0; j <= N-i-1; j++){
maxEndingHere = Math.max(maxEndingHere+M[row][col],0);
maxSoFar = Math.max(maxSoFar,maxEndingHere);
row--;
col++;
}
max = Math.max(max,maxSoFar);
}
// max over anti-diagonals
for(int i = 0; i < N; i++){
long maxSoFar = 0;
long maxEndingHere = 0;
int row = i;
int col = N-1;
for(int j = 0; j <= i; j++){
maxEndingHere = Math.max(maxEndingHere+M[row][col],0);
maxSoFar = Math.max(maxSoFar,maxEndingHere);
row--;
col--;
}
max = Math.max(max,maxSoFar);
}
// max over anti-diagonals 2
for(int i = 0; i < N; i++){
long maxSoFar = 0;
long maxEndingHere = 0;
int row = N-1;
int col = N-1;
for(int j = 0; j <= N-i-1; j++){
maxEndingHere = Math.max(maxEndingHere+M[row][col],0);
maxSoFar = Math.max(maxSoFar,maxEndingHere);
row--;
col--;
}
max = Math.max(max,maxSoFar);
}
return max;
}