题解 | #最长无重复子数组#
最长无重复子数组
http://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4
动态规划
dp[i] 表示 第i个结尾的最长无重复子数组的长度，dp[0]=1
因此针对dp[i+1],我们最多只要往前遍历 dp[i]个元素，dp[i+1]的长度len=1
往前遍历dp[i]个元素，如果不相等，则 len++,如果碰到相等则跳出循环
此时 dp[i+1] = len
dp[i+1] = 往前遍历dp[i]个元素时不相等的元素个数+1
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | publicintmaxLength (int[] arr) { // write code here //dp[i] 表示 第i个结尾的最长无重复 int[] dp = newint[arr.length]; dp[0] = 1; intmax = 1; for(inti=1;i<arr.length;i++){ intlen = 1; for(intj=i-1,k=dp[i-1];k>0;k--){ if(arr[i]!= arr[j--]){ len++; continue; } break; } dp[i] = len; max = Math.max(max,dp[i]); } returnmax; } |
