当前位置:首页 » Project Euler » 详细页

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).

−2532
9−651
3273
−18−4  8

Solution

首先按照给出的方式生成整个棋盘,直接模拟生成即可。 之后,枚举每一行、每一列,每一个从左侧开始的主对角线和次对角线、每一个从上侧开始的主对角线和次对角线,计算该序列的最大连续和即可。

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