#3630
Partition Array for Maximum XOR and AND
hard · 17.6% accepted · 31 likes · top 1%
array · math · greedy · bit manipulation · enumeration
Description
You are given an integer array nums.
Partition the array into three (possibly empty) subsequences A, B, and C such that every element of nums belongs to exactly one subsequence.
Your goal is to maximize the value of: XOR(A) + AND(B) + XOR(C)
where:
- XOR(arr) denotes the bitwise XOR of all elements in arr. If arr is empty, its value is defined as 0.
- AND(arr) denotes the bitwise AND of all elements in arr. If arr is empty, its value is defined as 0.
Return the maximum value achievable.
Note: If multiple partitions result in the same maximum sum, you can consider any one of them.
Solution