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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n):
        a = LI()

        m = {}
        def _f(a):
            l = len(a)
            if l < 2:
                return 0
            k = tuple(a)
            if k in m:
                return m[k]
            r = 0
            for i in range(len(a)-1):
                if abs(a[i]-a[i+1]) >= 2:
                    continue
                t = _f(a[:i] + a[i+2:]) + 2
                if r < t:
                    r = t
            m[k] = r
            return r

        return _f(a)

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))



print(main())

Python: # import sys
# input = lambda: sys.stdin.readline().rstrip()

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

        if n == 0:
            exit()
        w = list(map(int, input().split()))
        
        dp = [[0]*(n+1) for _ in range(n+2)]
        for gap in range(2,n+1):
            for l in range(n-gap+1):
                r = l + gap
                if dp[l+1][r-1] == gap-2:
                    if abs(w[l] - w[r-1]) <= 1:
                        dp[l][r] = gap
                    else:
                        dp[l][r] = gap - 2
                for k in range(l,r):
                    if dp[l][k] + dp[k][r] > dp[l][r]:
                            dp[l][r] = dp[l][k] + dp[k][r]
                    # dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r])
        # for i in range(n):
        #     print(*dp[i])
        print(dp[0][-1])
if __name__ == "__main__":
    resolve()

Python: def main(n):
    a = list(map(int, input().split()))
    dp = [[0] * (n+1) for i in range(n)]
    # 区間[l,r)の最大落とせる個数
    for i in range(n - 1):
        if abs(a[i] - a[i + 1]) <= 1:
            dp[i][i + 2] = 2
            # 隣り合う達磨weightが1以内のペアをdpに記録
    for i in range(2, n): # 区間の広さ, 最大で0番目とn-1番目の差
        for l in range(n-i): # 左側のとれる値は区間の広さに依存
            r = i+l+1 # 右側は上記2変数から計
            if abs(a[l] - a[r-1]) <= 1: # 今見ている左端と右端がweight 1以内の時
                if dp[l+1][r-1] == r-l-2: # 左右1個ずつ内側の最大落とせる個数が「全部落とせる」だったとき
                    dp[l][r] = r-l # dp[l][r]は左右端を追加して記録
                    continue
            res = dp[l+1][r-1] # とりあえず現在の左右1個ずつ内側の値を記録
            for li in range(l+1, r): # lとrの間のどこかで区切って「lから区切り」「区切りからr」までの和を出す
                tmp = dp[l][li] + dp[li][r] # 区間[l, li) と 区間[li, r)のdp和
                if res < tmp: #区切った場所が最大値を更新するのであればresを更新
                    res = tmp
            dp[l][r] = res
    print(dp[0][n]) # 左端 0 から右端 n-1 までの最大値を出す

if __name__ == "__main__":
    while 1:
        n = int(input())
        if n:
            main(n)
        else:
            break

Python: def main(n):
    a = list(map(int, input().split()))
    dp = [[0] * n for i in range(n)]
    for i in range(n - 1):
        if abs(a[i] - a[i + 1]) <= 1:
            dp[i][i + 1] = 2
    for i in range(2, n):
        for l in range(n - i):
            r = i + l
            res = 0
            if abs(a[l] - a[r]) <= 1:
                if dp[l + 1][r - 1] == r - l - 1:
                    dp[l][r] = r - l + 1
                    continue
            res = dp[l + 1][r - 1]
            for li in range(l + 1, r):
                tmp = dp[l][li] + dp[li + 1][r]
                if res < tmp:
                    res = tmp
            dp[l][r] = res
    print(dp[0][n-1])
    def dfs(l, r):
        if l >= r: return 0
        if dp[l][r] != -1: return dp[l][r]
        if abs(a[l] - a[r]) <= 1:
            if dfs(l + 1, r - 1) == r - l - 1:
                dp[l][r] = r - l + 1
                return r - l + 1
        res = 0
        for li in range(l + 1, r):
            tmp = 0
            f = 0
            if dp[l][li] != -1:
                tmp += dp[l][li]
            else:
                tmp += dfs(l, li)
            if dp[li + 1][r] != -1:
                tmp += dp[li + 1][r]
            else:
                tmp += dfs(li + 1, r)
            if res < tmp:
                res = tmp
        dp[l][r] = res
        return res
    # print(dfs(0, n - 1))


if __name__ == "__main__":
    while 1:
        n = int(input())
        if n:
            main(n)
        else:
            break

Python: 
from functools import lru_cache
while True:
    N = int(input())
    if N==0:
        break
    W = list(map(int, input().split()))
    assert len(W) == N


    @lru_cache(maxsize=None)
    def solve(l, r):
        assert l<=r
        if (r-l)%2==1:
            return False
        if r-l==2:
            return abs(W[l]-W[l+1])<=1
        return (solve(l, r-2) and solve(r-2, r)) \
            or (solve(l, l+2) and solve(l+2, r)) \
            or (solve(l+1, r-1) and abs(W[l]-W[r-1])<=1)


    dp = [0]*(N+1)
    for i in range(1, N+1):
        ma = 0
        for j in range(i-1, -1, -1):
            ma = max(ma, dp[j]+solve(j, i)*(i-j))
        dp[i] = ma

    print(dp[-1])