XorAndLIS | Topcoder Archive

Problem Statement

Let LIS(S) denote the length of the longest increasing subsequence of the sequence S. Note that the subsequence does not have to be contiguous. For example, for S1 = {10,0,20,0,30} we have LIS(S1) = 3 and for S2 = {1,1,1} we have LIS(S2) = 1.

You are given a long[] x: a sequence of nonnegative integers. You are allowed to modify this sequence by performing a sequence of zero or more updates. In each update, you select an index i between 0 and |x|-2, inclusive, and you change x[i+1] into (x[i+1] xor x[i]).

Your goal is to make LIS(x) as large as possible. Please compute and return this maximal value.

Definition

Class:: XorAndLIS
Method:: maximalLength
Parameters:: long[]
Returns:: int
Method signature:: int maximalLength(long[] x)
(be sure your method is public)

Constraints

x will contain between 1 and 100 elements, inclusive.
Each element in x will be between 0 and 10^18, inclusive.

Examples

```
{4,2,1}
```
```
Returns: 3
```
You can do x[1] = x[1] xor x[0], the sequence will be {4,6,1}. Then you do x[2] = x[2] xor x[1] and the sequence becomes {4,6,7}.
```
{0,0,0,0,0,0,0,0,0,0}
```
```
Returns: 1
```
Whatever you do, the sequence never changes, and the LIS is 1.
```
{1,2,3,4,5,6,7,8,9,10}
```
```
Returns: 10
```
This time you don't need to do anything.
```
{7,3,1}
```
```
Returns: 2
```

{1008,42,7,5,2,9,75,0,0,12,3,6,81,4,3}

Returns: 12

```
{1000000000000000000}
```
```
Returns: 1
```
```
{10000000000,10000000001}
```
```
Returns: 2
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.