Go, straightforward DP with comments


  • 0
    A
    
    type r struct{ h, v, a, d int }
    
    func longestLine(M [][]int) int {
    	max := func(i ...int) int {
    		for _, j := range i {
    			if j > i[0] {
    				i[0] = j
    			}
    		}
    		return i[0]
    	}
    
    	maxLen := 0
    	dp := make([][]r, len(M))
    	_dp := func(i, j int) r { // _dp is just a bounds-checked accessor for dp
    		if i < 0 || j < 0 || i >= len(dp) || j >= len(dp[i]) {
    			return r{} // return all zeros for out of bounds
    		}
    		return dp[i][j]
    	}
    
    	for i, m := range M {
    		dp[i] = make([]r, len(m))
    		for j, x := range m { // x = M[i][j]
    			dp[i][j].h = _dp(i, j-1).h*x + x   // horizontal
    			dp[i][j].v = _dp(i-1, j).v*x + x   // vertical
    			dp[i][j].d = _dp(i-1, j-1).d*x + x // diagonal \
    			dp[i][j].a = _dp(i-1, j+1).a*x + x // anti-diagonal /
    			maxLen = max(maxLen, dp[i][j].h, dp[i][j].v, dp[i][j].d, dp[i][j].a)
    		}
    	}
    
    	return maxLen
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.