Go: package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

const (
	initialBufSize = 10000000
	maxBufSize     = 100000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords) // bufio.ScanLines
	return sc
}

func main() {
	sc = initScanner(os.Stdin)
	resolve()
}

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	a, _ := strconv.Atoi(sc.Text())
	return int(a)
}
func nextString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextIntSlice(sc *bufio.Scanner, n int) (a []int) {
	a = make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = nextInt(sc)
	}
	return a
}

var dp [][]int

func initDP(n int) {
	dp = make([][]int, n+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n+1)
		for j := 0; j < len(dp[0]); j++ {
			dp[i][j] = -1
		}
	}
}

func resolve() {
	ans := []int{}
	for true {
		n := nextInt(sc)
		if n == 0 {
			break
		}
		as := nextIntSlice(sc, n)
		initDP(n)
		_rec(as, n, 0, n)
		ans = append(ans, dp[0][n])
	}
	for _, v := range ans {
		fmt.Println(v)
	}
	return
}

func _rec(as []int, n, l, r int) int {
	if dp[l][r] > -1 {
		return dp[l][r]
	}
	if r-l == 1 { // prevent to hit daruma
		dp[l][r] = 0
		return dp[l][r]
	}
	if r-l == 2 {
		if abs(as[l]-as[r-1]) <= 1 {
			dp[l][r] = 2
		} else {
			dp[l][r] = 0
		}
		return dp[l][r]
	}
	if abs(as[l]-as[r-1]) <= 1 {
		v := _rec(as, n, l+1, r-1)
		// if we can remove internal blocks
		if (r - 1 - (l + 1)) == v {
			dp[l][r] = v + 2
			return dp[l][r]
		} else {
			dp[l][r] = v
		}
	}
	for i := l + 1; i < r; i++ {
		v := _rec(as, n, l, i) + _rec(as, n, i, r)
		if dp[l][r] < v {
			dp[l][r] = v
		}
	}
	return dp[l][r]
}

func abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}

Python: import sys


def main():
    while True:
        n = int(input())

        # nが0なら処理終わり
        if n == 0:
            sys.exit()

        arr = list(map(int, input().split()))

        # dpテーブル
        dp = [[0] * n for _ in range(n)]

        # dはdistance。lとrが1〜n-1離れている場合を順に考えていく
        for d in range(1, n):

            # distanceに応じてleftのレンジが変化する
            for l in range(n - d):

                # rは当然left+distance
                r = l + d

                # もしdistanceが奇数なら、1個内側を見ればいい
                if d % 2 == 1:

                    # left, rightの内側が全部叩き出せる場合
                    if dp[l + 1][r - 1] == d - 1 and abs(arr[l] - arr[r]) <= 1:
                        dp[l][r] = dp[l + 1][r - 1] + 2

                    # 叩けないブロックがある場合はワーシャルフロイドっぽく解く
                    else:
                        for k in range(l + 1, r):
                            tmp = dp[l][k] + dp[k + 1][r]
                            if tmp > dp[l][r]:
                                dp[l][r] = tmp

                # もしdistanceが偶数なら、大きい方を採用するだけ
                else:
                    dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])

        print(dp[0][-1])


if __name__ == '__main__':
    main()

Python: def solve(n,lst):
    #i行j列はjから連続したi個のうち落とせる個数の最大値
    dp=[[0]*n for _ in range(n+1)]

    #initialize
    for j in range(n-1):
        if abs(lst[j]-lst[j+1])<=1 : dp[2][j]=2
    

    #真ん中2*i個が抜けて上下を落とせる場合と2*(i+1)個を複数の部分に分けて落とせる場合の2通りが考えられる
    for i in range(3,n+1):
        for j in range(n-i+1):
            mx=0
            if i%2==0:
                if abs(lst[j]-lst[j+i-1])<=1:
                    if dp[i-2][j+1]==i-2:
                        dp[i][j]=i
                        continue
                mx=dp[i-2][j+1]                
                for k in range(2,i,2):
                    if mx<dp[k][j]+dp[i-k][j+k]:
                        mx=dp[k][j]+dp[i-k][j+k]
                        if mx==i:break
            else :
                for k in range(1,i,2):
                    if mx<dp[k][j]+dp[i-k][j+k]:
                        mx=dp[k][j]+dp[i-k][j+k]                
            dp[i][j]=mx
    print(dp[n][0])        
    #print(dp) 

                

while 1:
    n=int(input())
    if n==0 : break
    lst=tuple(map(int,input().split()))
    solve(n,lst)

Python: # coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


def solve(n, W):
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for w in range(2, n + 1):
        for l in range(n):
            r = l + w
            if r > n: continue

            if dp[l + 1][r - 1] == w - 2 and abs(W[l] - W[r - 1]) <= 1:
                dp[l][r] = w

            for mid in range(l, r):
                dp[l][r] = max(dp[l][r], dp[l][mid] + dp[mid][r])
            # print(l, r, dp)

    return dp[0][n]


while 1:
    n = int(input())
    W = inpl()
    if n == 0:
        exit()
    print(solve(n, W))

Python: import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
while True:
    N = int(input())
    if not N:
        break
    W = [int(x) for x in input().split()]
    dp = [[0] * N for _ in range(N)]
    for i in range(N-1):
        if abs(W[i] - W[i + 1]) <= 1:
            dp[i][i + 1] = 2
    for w in range(3, N + 1):
        for left in range(N - w + 1):
            # [left, right]
            right = left + w - 1
            if right - left - 1 == dp[left + 1][right - 1] and abs(W[left] - W[right]) <= 1:
                dp[left][right] = right - left + 1
                continue
            for mid in range(left + 1, right):
                m = dp[left][mid] + dp[mid + 1][right]
                if m > dp[left][right]:
                    dp[left][right] = m
    print(dp[0][N-1])