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: n=int(input())
while n!=0:
    w=list(map(int,input().split()))
    check=[[False]*n for i in range(n)]
    for i in range(n-1):
        if abs(w[i+1]-w[i])<=1:
            check[i][i+1]=True
    for i in range(3,n,2):
        for j in range(n-i):
            for k in range(j+1,j+i):
                if check[j][j+i]==False and check[j][k] and check[k+1][j+i]:
                    check[j][j+i]=True
                    break
            if check[j][j+i]==False and abs(w[j]-w[j+i])<=1 and check[j+1][j+i-1]:
                check[j][j+i]=True
    dp=[0]*(n+1)
    for k in range(n):
        for m in range(k):
            if check[m][k]:
                dp[k]=max(dp[k],dp[m-1]+k-m+1)
        dp[k]=max(dp[k],dp[k-1])
    print(dp[n-1])
    n=int(input())

Python: def main():
  while True:
    n = int(input())
    if n == 0:
      break
    wlst = list(map(int, input().split()))
    connect = [[None] * n for _ in range(n)]
    for i in range(n):
      for j in range(n):
        connect[i][j] = abs(wlst[i] - wlst[j]) <= 1
    
    max_lst = [[False] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
      max_lst[0][i] = True
    
    dp = [[0] * n for _ in range(n + 1)]
    
    def check(length, left):
      ret = dp[length - 1][left]
      for k in range(length - 1, 0, -2):
        if not max_lst[length - k - 1][left + k]:continue
        if connect[left + k - 1][left + length - 1]:
          temp = length - k + 1 + dp[k - 1][left]
          if ret < temp:
            ret = temp
      return ret
    
    for length in range(2, n + 1):
      for left in range(n - length + 1):
        dp[length][left] = check(length, left)
        if dp[length][left] == length:
          max_lst[length][left] = True
    
    print(dp[n][0])

main()

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

def main():
  while True:
    n = int(input())
    if(n == 0):
      break
    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
            continue
        for k in range(l, r):
          if(dp[l][r] < dp[l][k]+dp[k][r]):
            dp[l][r] = dp[l][k]+dp[k][r]
    print(dp[0][n])
    
if __name__ == '__main__':
  main()

Python: import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def ti(): return tuple(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

## DP

def solve(N):
    A = ti()
    dp = dp2(0, N, N)

    for i in range(N-1):
        if abs(A[i]-A[i+1]) < 2:
            dp[i][i+1] = 2
    
    for h in range(2, N): #hは(区間の長さ)-1
        for i in range(N):
            if i+h >= N:
                break
            j = i+h
            # 区間の長さが偶数の場合
            if h % 2:
                if abs(A[i]-A[j]) < 2 and dp[i+1][j-1] == h-1:
                    dp[i][j] = h + 1
                    continue
                else:
                    dp[i][j] = max(tuple(dp[i][k]+dp[k+1][j] for k in range(i, j)))
            # 区間の長さが奇数の場合
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        else:
            continue

    print(dp[0][N-1])

while True:
    N = ii()
    if N == 0:
        exit()
    solve(N)

Python: n = int(input())
if n == 0:
    break
w = list(map(int, input().split()))
dp = [[-1 for j in range(n + 1)] for i in range(n + 1)]


def rec(l, r):
    # 既に計算済み？
    if dp[l][r] != -1:
        return dp[l][r]

    # これ以上取り除けない？
    if abs(l - r) <= 1:
        return 0

    res = 0
    # パターン1.
    if abs(w[l] - w[r - 1]) <= 1 and rec(l + 1, r - 1) == r - l - 2:
        res = r - l

    # パターン２.区間を分ける
    for mid in range(l + 1, r - 1):
        res = max(res, rec(l, mid) + rec(mid, r))

    dp[l][r] = res
    return res


print(rec(0, n))

Python: 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 w in range(2, 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):
                dp[left][right] = max(dp[left][right], dp[left][mid] + dp[mid + 1][right])
    print(dp[0][N-1])