|
| 1 | +/** |
| 2 | + * A sequence X_1, X_2, ..., X_n is fibonacci-like if: |
| 3 | + * n >= 3 |
| 4 | + * X_i + X_{i+1} = X_{i+2} for all i + 2 <= n |
| 5 | + * |
| 6 | + * Given a strictly increasing array A of positive integers forming a sequence, |
| 7 | + * find the length of the longest fibonacci-like subsequence of A. |
| 8 | + * If one does not exist, return 0. |
| 9 | + * |
| 10 | + * (Recall that a subsequence is derived from another sequence A by deleting |
| 11 | + * any number of elements (including none) from A, without changing the order |
| 12 | + * of the remaining elements. For example, [3, 5, 8] is a subsequence of |
| 13 | + * [3, 4, 5, 6, 7, 8].) |
| 14 | + * |
| 15 | + * Example 1: |
| 16 | + * Input: [1,2,3,4,5,6,7,8] |
| 17 | + * Output: 5 |
| 18 | + * Explanation: |
| 19 | + * The longest subsequence that is fibonacci-like: [1,2,3,5,8]. |
| 20 | + * |
| 21 | + * Example 2: |
| 22 | + * Input: [1,3,7,11,12,14,18] |
| 23 | + * Output: 3 |
| 24 | + * Explanation: |
| 25 | + * The longest subsequence that is fibonacci-like: |
| 26 | + * [1,11,12], [3,11,14] or [7,11,18]. |
| 27 | + * |
| 28 | + * Note: |
| 29 | + * |
| 30 | + * 3 <= A.length <= 1000 |
| 31 | + * 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9 |
| 32 | + * (The time limit has been reduced by 50% for submissions in Java, C, and C++.) |
| 33 | + */ |
| 34 | + |
| 35 | + |
| 36 | +publicclassLengthOfLongestFibonacciSubsequence873 { |
| 37 | +publicintlenLongestFibSubseq(int[]A) { |
| 38 | +intlen =A.length; |
| 39 | +intlongest =Integer.MIN_VALUE; |
| 40 | +for (inti=0;i<len-3;i++) { |
| 41 | +for (intj=i+1;j<len-2;j++) { |
| 42 | +inta =A[i]; |
| 43 | +intb =A[j]; |
| 44 | +intidx =Arrays.binarySearch(A,j+1,len,a +b); |
| 45 | +if (idx <0)continue; |
| 46 | +intl =2; |
| 47 | +while (idx >=0 &&idx <len) { |
| 48 | +l++; |
| 49 | +a =b; |
| 50 | +b =A[idx]; |
| 51 | +if (idx >=len)break; |
| 52 | +idx =Arrays.binarySearch(A,idx +1,len,a +b); |
| 53 | + } |
| 54 | +if (l >longest) { |
| 55 | +longest =l; |
| 56 | + } |
| 57 | + } |
| 58 | + } |
| 59 | +returnlongest ==Integer.MIN_VALUE ?0 :longest; |
| 60 | + } |
| 61 | + |
| 62 | + |
| 63 | +publicintlenLongestFibSubseq2(int[]A) { |
| 64 | +intN =A.length; |
| 65 | +int[][]dp =newint[N +1][N +1]; |
| 66 | +intres =0; |
| 67 | +for (inti=2;i<N;i++) { |
| 68 | +for (intj=i+1;j<=N;j++) { |
| 69 | +inttoBeFound =A[j-1] -A[i-1]; |
| 70 | +if (toBeFound >A[i-2])break; |
| 71 | +intidx =Arrays.binarySearch(A,0,i-1,toBeFound); |
| 72 | +if (idx >=0) { |
| 73 | +if (dp[idx+1][i] ==0) { |
| 74 | +dp[i][j] =3; |
| 75 | + }else { |
| 76 | +dp[i][j] +=dp[idx+1][i] +1; |
| 77 | + } |
| 78 | + } |
| 79 | +if (dp[i][j] >res)res =dp[i][j]; |
| 80 | + } |
| 81 | + } |
| 82 | +returnres; |
| 83 | + } |
| 84 | + |
| 85 | + |
| 86 | +publicintlenLongestFibSubseq3(int[]A) { |
| 87 | +intN =A.length; |
| 88 | +Map<Integer,Integer>index =newHashMap(); |
| 89 | +for (inti =0;i <N; ++i)index.put(A[i],i); |
| 90 | +int[][]dp =newint[N +1][N +1]; |
| 91 | +intres =0; |
| 92 | +for (inti=2;i<N;i++) { |
| 93 | +for (intj=i+1;j<=N;j++) { |
| 94 | +inttoBeFound =A[j-1] -A[i-1]; |
| 95 | +if (toBeFound >A[i-2])break; |
| 96 | +if (index.containsKey(toBeFound)) { |
| 97 | +intidx =index.get(toBeFound); |
| 98 | +if (dp[idx+1][i] ==0) { |
| 99 | +dp[i][j] =3; |
| 100 | + }else { |
| 101 | +dp[i][j] +=dp[idx+1][i] +1; |
| 102 | + } |
| 103 | + } |
| 104 | +if (dp[i][j] >res)res =dp[i][j]; |
| 105 | + } |
| 106 | + } |
| 107 | +returnres; |
| 108 | + } |
| 109 | + |
| 110 | + |
| 111 | +/** |
| 112 | + * https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/solution/ |
| 113 | + */ |
| 114 | +publicintlenLongestFibSubseq4(int[]A) { |
| 115 | +intN =A.length; |
| 116 | +Map<Integer,Integer>index =newHashMap(); |
| 117 | +for (inti =0;i <N; ++i) |
| 118 | +index.put(A[i],i); |
| 119 | + |
| 120 | +Map<Integer,Integer>longest =newHashMap(); |
| 121 | +intans =0; |
| 122 | + |
| 123 | +for (intk =0;k <N; ++k) { |
| 124 | +for (intj =0;j <k; ++j) { |
| 125 | +inti =index.getOrDefault(A[k] -A[j], -1); |
| 126 | +if (i >=0 &&i <j) { |
| 127 | +// Encoding tuple (i, j) as integer (i * N + j) |
| 128 | +intcand =longest.getOrDefault(i *N +j,2) +1; |
| 129 | +longest.put(j *N +k,cand); |
| 130 | +ans =Math.max(ans,cand); |
| 131 | + } |
| 132 | + } |
| 133 | + } |
| 134 | +returnans >=3 ?ans :0; |
| 135 | + } |
| 136 | + |
| 137 | + |
| 138 | +/** |
| 139 | + * https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/discuss/152343/C++JavaPython-Check-Pair |
| 140 | + */ |
| 141 | +publicintlenLongestFibSubseq5(int[]A) { |
| 142 | +Set<Integer>s =newHashSet<Integer>(); |
| 143 | +for (intx :A)s.add(x); |
| 144 | +intres =2; |
| 145 | +for (inti =0;i <A.length; ++i) { |
| 146 | +for (intj =i +1;j <A.length; ++j) { |
| 147 | +inta =A[i],b =A[j],l =2; |
| 148 | +while (s.contains(a +b)) { |
| 149 | +b =a +b; |
| 150 | +a =b -a; |
| 151 | +l++; |
| 152 | + } |
| 153 | +res =Math.max(res,l); |
| 154 | + } |
| 155 | + } |
| 156 | +returnres >2 ?res :0; |
| 157 | + } |
| 158 | + |
| 159 | + |
| 160 | +/** |
| 161 | + * https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/discuss/152343/C++JavaPython-Check-Pair |
| 162 | + */ |
| 163 | +publicintlenLongestFibSubseq6(int[]A) { |
| 164 | +intres =0; |
| 165 | +int[][]dp =newint[A.length][A.length]; |
| 166 | +Map<Integer,Integer>index =newHashMap<>(); |
| 167 | +for (intj =0;j <A.length;j++) { |
| 168 | +index.put(A[j],j); |
| 169 | +for (inti =0;i <j;i++) { |
| 170 | +intk =index.getOrDefault(A[j] -A[i], -1); |
| 171 | +dp[i][j] = (A[j] -A[i] <A[i] &&k >=0) ?dp[k][i] +1 :2; |
| 172 | +res =Math.max(res,dp[i][j]); |
| 173 | + } |
| 174 | + } |
| 175 | +returnres >2 ?res :0; |
| 176 | + } |
| 177 | + |
| 178 | +} |