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: 
def main():
    while True:
        N = int(input())
        if N == 0:
            exit()
        A = list(map(int,input().split()))
        can_drop = [[False] * N for _ in range(N)]
        # d[i]: i個のブロック列で最大何個落とせるか
        d = [0] * (N+1)

        # 隣接するのが落とせるかどうか
        for i in range(N-1):
            if abs(A[i] - A[i+1]) <= 1:
                can_drop[i][i+1] = True

        # 何個分をみるか。一個増えても落とせるやつ個数が増えたりしないので２刻み
        for i in range(3, N, 2):
            # どのブロックはじめで見るか。
            for j in range(N-i):
                # 間
                last = j + i
                for k in range(j+1, j+i):
                    # j~lastまでで落とせないが、j~k, k+1~lastに分けてみると、両方の部分で結果的にj~lastで落とせる場合
                    if not can_drop[j][last] and can_drop[j][k] and can_drop[k+1][last]:
                        can_drop[j][last] = True
                        break
                # j ~ lastで落ちないが、j+1~last-1で落とせて、jとlastの差が１以下の場合は、j~lastで落とせると言える
                if not can_drop[j][last] and can_drop[j+1][last-1] and abs(A[j] - A[last]) <= 1:
                    can_drop[j][last] = True

        # can_dropのTrueが続いている最長部分を探す
        for i in range(N):
            for j in range(N):
                if can_drop[j][i]:
                    d[i] = max(d[i], d[j-1] + i - j + 1)
        
            d[i] = max(d[i], d[i - 1])
        print(d[N-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: import sys
input = sys.stdin.readline

def func():
    while True:
        N = int(input())
        if N == 0: break
        W = [int(i) for i in input().split()]
        
        dp = [[0]*(N+1) for j in range(N+1)]

        for s in range(2, N+1):
            for l in range(N-s+1):
                r = l + s
                if (s - 2) % 2 == 0:
                    if dp[l+1][r-1] == s-2 and abs(W[l] - W[r-1]) <= 1:
                        dp[l][r] = s
                        continue
                for i in range(l, r+1):
                    if dp[l][r] < dp[l][i] + dp[i][r]:
                        dp[l][r] = dp[l][i] + dp[i][r]

        print(dp[0][N])

if __name__ == "__main__":
    func()

Python: def solve(n,w):
    dp=[[0]*(n+1) for _ in range(n+1)]
    for kukan in range(2,n+1):
        for l in range(0,n+1-kukan):
            r=l+kukan
            #decide dp[l][l+kukan]
            if (kukan-2)%2==0:
                if abs(w[l]-w[r-1])<=1 and dp[l+1][r-1]==r-l-2:
                    dp[l][r]=dp[l+1][r-1]+2
                    continue
            for i in range(l+1,r):
                if dp[l][r]<(dp[l][i]+dp[i][r]):
                    dp[l][r]=dp[l][i]+dp[i][r]
    return dp[0][n]
            

n=int(input())
while(n!=0):
    w=list(map(int,input().split()))
    print(solve(n,w))
    n=int(input())

Python: n = int(input())
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
    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 n == 0:
    break
  wlst = list(map(int, input().split()))
  dp = [[0] * n for _ in range(n + 1)]
  
  def check(left1, right1, left2, right2, cnt):
    if left1 > right1 and left2 > right2: return cnt
    if left1 > right1:return dp[right2 - left2 + 1][left2] + cnt
    if left2 > right2:return dp[right1 - left1 + 1][left1] + cnt
    ret = cnt + dp[right1 - left1 + 1][left1] + dp[right2 - left2 + 1][left2]
    if abs(wlst[right1] - wlst[left2]) <= 1:
      ret = max(ret, check(left1, right1 - 1, left2 + 1, right2, cnt + 1))
    if right1 - left1 + 1 >= 2 and dp[2][right1 - 1]:
      ret = max(ret, check(left1, right1 - 2, left2, right2, cnt + 1))
    if right2 - left2 + 1 >= 2 and dp[2][left2]:
      ret = max(ret, check(left1, right1, left2 + 2, right2, cnt + 1))
    return ret
  
  for length in range(2, n + 1):
    for left in range(n - length + 1):
      for k in range(length - 1):
        dp[length][left] = max(dp[length][left], check(left, left + k, left + k + 1, left + length - 1, 0))
  
  print(dp[n][0] * 2)

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

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+1)]
    
    for gap in range(2,n+1):
      #gapが小さい方から埋めることで漏れをなくす
      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])
    #print(dp)
    
if __name__ == '__main__':
  main()