【动态规划】 | #最长无重复子数组#

确定dp含义:dp数组代表以arr[i]结尾的最大无重复子数组

初始状态:dp[0] = 0 ，没数字肯定长度为0

转换方程:所以我们可以将arr[i]和离arr[i]最近的相等数字的距离与上一个dp[i - 1]的距离相比较，就可以知道重复的数字究竟是否包含在上一次最大的dp[i - 1]中。

if(不存在重复(j == -1)){
	dp[i] = dp[i - 1] + 1;//不存在重复直接+1
}else{
	if(重复的字符包含于dp[i - 1]的子串里(dp[i - 1] >= i - j - 1)){
    	dp[i] = i - j - 1;//因为存在重复的字符了，所以得由重复字符j所在位置决定
    }else if(不存在dp[i - 1]子串中(dp[i - 1] < i - j - 1)){
    	dp[i] = dp[i - 1] + 1;
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
   public int maxLength (int[] arr) {
        int len = arr.length;
        int[] dp = new int[len + 1];
        if(len == 0){
            return 0;
        }
        dp[0] = 0;
        //j代表i左边第一个和i相等的元素
        //dp代表以i为结尾的最长无重复子数组
        int max = 0;
        for(int i = 1;i <= arr.length;i++){
            int j;
            for(j = i - 2;j >= 0;j--){
                if(j >= 0 && arr[j] == arr[i - 1]){
                    break;
                }
            }
            if(j == -1){
                dp[i] = dp[i - 1] + 1;
            }else{
                if(dp[i - 1] < i - j - 1){
                    dp[i] = dp[i - 1] + 1;
                }else{
                    dp[i] = i - j - 1;
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}