### Searching for a maximum-sum subsequence题号：149 难度： 50 中英对照

Looking at the table below, it is easy to verify that the maximum possible sum of adjacent numbers in any direction (horizontal, vertical, diagonal or anti-diagonal) is 16 (= 8 + 7 + 1).

 −2 5 3 2 9 −6 5 1 3 2 7 3 −1 8 −4 8

### Code

public final class p149 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static final int SIZE = 2000;

static private int[][] grid;

static public String run() {
// Fill the grid
grid = new int[SIZE][SIZE];
LfgRandom rand = new LfgRandom();
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[y].length; x++)
grid[y][x] = rand.next();
}

// Scan along all line directions and positions
int max = 0;
for (int i = 0; i < SIZE; i++) {
max = Math.max(getMaxSubstringSum(0, i, +1,  0), max);  // Horizontal from left edge
max = Math.max(getMaxSubstringSum(i, 0,  0, +1), max);  // Vertical from top edge
max = Math.max(getMaxSubstringSum(0, i, +1, +1), max);  // Diagonal from left edge
max = Math.max(getMaxSubstringSum(i, 0, +1, +1), max);  // Diagonal from top edge
max = Math.max(getMaxSubstringSum(i, 0, -1, +1), max);  // Anti-diagonal from top edge
max = Math.max(getMaxSubstringSum(SIZE - 1, i, -1, +1), max);  // Anti-diagonal from right edge
}
return Integer.toString(max);
}

// For the sequence of numbers in the grid at positions (x, y), (x+dx, y+dy), (x+2*dx, y+2*dy), ... until the
// last in-bounds indices, this function returns the maximum sum among all possible substrings of this sequence.
static private int getMaxSubstringSum(int x, int y, int dx, int dy) {
int max = 0;
for (int cur = 0; 0 <= x && x < SIZE && 0 <= y && y < SIZE; x += dx, y += dy) {
cur = Math.max(cur + grid[y][x], 0);  // Reset the running sum if it goes negative
max = Math.max(cur, max);  // Keep track of the best seen running sum
}
return max;
}

// Lagged Fibonacci generator
static class LfgRandom {

// Circular buffer
private int[] history;
private int index;

private int k;  // The 1-based index of the next sequence item, but saturates at 56

public LfgRandom() {
k = 1;
history = new int[55];
index = 0;
}

public int next() {
int result;
if (k <= 55) {
result = (int)((100003L - 200003L*k + 300007L*k*k*k) % 1000000) - 500000;
k++;
} else {
result = (getHistory(24) + getHistory(55) + 1000000) % 1000000 - 500000;
// Don't increment k, to prevent overflow
}
history[index] = result;
index = (index + 1) % history.length;
return result;
}

// Returns the number that was generated n steps ago, where 1 <= n <= history.length.
private int getHistory(int n) {
if (n <= 0 || n > history.length)
throw new IllegalArgumentException();
return history[(index - n + history.length) % history.length];
}

}

}
52852124
351ms