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()
        l = len(a)
        s = set()
        r = 0
        for i in range(l-1):
            if abs(a[i] - a[i+1]) < 2:
                s.add((i,i+1))
        for i in range(4, l+1):
            for j in range(l-i+1):
                k = j + i - 1
                if (j+1, k-1) in s and abs(a[j] - a[k]) < 2:
                    s.add((j,k))
                    continue
                for m in range(j+2,k,2):
                    if (j,m-1) in s and (m,k) in s:
                        s.add((j,k))
                        break

        m = {}
        m[l] = 0
        def _f(i):
            if i in m:
                return m[i]
            r = 0
            for j in range(i,l+1):
                t = _f(j+1)
                if (i,j) in s:
                    t += j - i + 1
                if r < t:
                    r = t
            m[i] = r
            return r
        return _f(0)

    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())
        w = list(map(int, input().split()))
        if n==0:
            break
        else:
            dp = [[0]*(n+1) for _ in range(n+2)]
            # 幅
            for i in range(2, n+1):
                for l in range(n-i+1):
                    r = l+i
                    if dp[l+1][r-1] == i-2:
                        if abs(w[l]-w[r-1])<=1:
                            dp[l][r] = i
                        else:
                            dp[l][r] = i-2
                    for j in range(l, r):
                        if dp[l][j] + dp[j][r] > dp[l][r]:
                            dp[l][r] = dp[l][j] + dp[j][r]

            print(dp[0][-1])        

if __name__ == '__main__':
    resolve()

C++: #include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H, L, R;
long long int ans;

using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin >> N;
	while (N) {
		vector<int>num(N);
		for (int i = 0; i < N; i++)cin >> num[i];
		vector<vector<int>>dp(N, vector<int>(N,0));
		for (int i = 0; i < N - 1; i++) {
			if (abs(num[i] - num[i + 1]) < 2)dp[i][i + 1] = 2;
		}
		for (int i = 4; i <= N; i += 2) {
			for (int j = 0; i + j <= N; j++) {
				for (int k = j; k < i + j - 1; k+=2) {
					for (int l = k + 1; l <= i + j - 1; l+=2) {
						if (!k) {
							if (dp[k + 1][l - 1] == l - k - 1) {
								if (l == N - 1) {
									if (abs(num[k] - num[l]) < 2) {
										dp[j][i + j - 1] = i;
									//	cout << j << " " << i + j - 1 << " " << dp[j][i + j - 1] << endl;
									}
								}
								else if(dp[l + 1][i + j - 1] == i + j - 1 - l&&abs(num[k] - num[l]) < 2) {
									dp[j][i + j - 1] = i;
									//cout << j << " " << i + j - 1 << " " << dp[j][i + j - 1] << endl;
								}
							}
						}
						else if (dp[j][k - 1] == k - j) {
							if (dp[k + 1][l - 1] == l - k - 1) {
								if (l == N - 1) {
									if (abs(num[k] - num[l]) < 2) {
										dp[j][i + j - 1] = i;
									//	cout << j << " " << i + j - 1 << " " << dp[j][i + j - 1] << endl;
									}
								}
								else if (dp[l + 1][i + j - 1] == i + j - 1 - l&&abs(num[k] - num[l]) < 2) {
									dp[j][i + j - 1] = i;
								//	cout << j << " " << i + j - 1 << " " << dp[j][i + j - 1] << endl;
								}
							}
						}
					}
				}
			}
		}
		ans = 0;
		vector<int>ret(N,0);
		ret[1] = dp[0][1];
		for (int i = 2; i < N; i++) {
			ret[i] = dp[0][i];
			for (int j = i - 1; j >= 1; j--) {
				ret[i] = max(ret[i], ret[j - 1] + dp[j][i]);
			}
			ans = max((int)ans,ret[i]);
		}
		cout << ans << endl;
		cin >> N;
	}
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int N;
int W[305];
int dp[305][305];
int main()
{
	while(true){
		scanf("%d",&N);
		if(N==0){break;}
		for(int i=0;i<N;i++){
			scanf("%d",&W[i]);
		}
		for(int i=0;i<305;i++){
			for(int j=0;j<305;j++){
				dp[i][j]=0;
			}
		}
		for(int i=0;i<=N-2;i++){
			if(abs(W[i]-W[i+1])<=1){dp[i][2]=2;}
		}
		for(int j=3;j<=N;j++){
			for(int i=0;i+j<=N;i++){
				//[i,i+j)
				for(int k=0;k<=j;k++){
					dp[i][j]=max(dp[i][k]+dp[i+k][j-k],dp[i][j]);
				}
				if(abs(W[i]-W[i+j-1])<=1&&dp[i+1][j-2]==j-2){
					dp[i][j]=max(dp[i][j],dp[i+1][j-2]+2);
				}
			}
		}
		/*
		for(int j=0;j<12;j++){
			for(int i=0;i+j<=12;i++){
				printf("%d ",dp[i][j]);
			}
			printf("\n");
		}*/
		/*
		for(int i=150;i>=0;i-=2){
		printf("%d\n",dp[i][299-i]);
		}*/
		printf("%d\n",dp[0][N]);
	}
	return 0;
}