Mgiyuk

Maximal unique continuous subsequence Given a sequence of integer numbers: a[0], a[1], a[2], ..., a[n] Subsequence a[i]...a[j] is unique if the following is true: a[i]...a[j] for each x, y between i and j and x != y: a[x] != a[y] I need to find length of maximal unique , continuous subsequence My approaches: I tried many heuristic approaches, but they didn't work. Then I wrote bruteforce, it gave O(n^3) complexity, which is impossible to calc if n = 10^6 O(n^3) n = 10^6 ans = 1 for i in [0, n] for j in [i, n] if unique a[i]...a[j] ans = max(ans, j-i+1) I think it is typical dp problem, but don't know how to proceed dp 4 Answers 4 Create hashmap (or use boolean array if range of values is rather short). Make two indexes - left and right , set them in the beginning. left right Move right index. At every step check if t = A[right] already is in map. Stop when ...