Sub-sequences (ICPC 2011 Amritapuri Online Contest)
Problem Statement: You are given a sequence of N numbers A[1..N]. Consider a sub-sequence (of continuous or non-continuous elements in the same order as given) such that the bitwise AND of all the numbers of the sub-sequence is equal to the bitwise OR of all the numbers of the sub-sequence. Amongst all such sub-sequences, find the sub-sequence that has the maximum sum of the numbers, and print this maximum sum.
Limits: 1<=A[i]<=10000
Hmm. So what are your first thoughts? You want to traverse over all the sub-sequences? Wrong! That would take hell lot of time. We’ll do it in O(n). All you need to do is pay attention to the properties of the bitwise AND and bitwise OR operator. These are two mutually exclusive operators. By using this term here, I mean to specify that no two different numbers can have the same result after their OR or AND. You can prove this by taking a few examples (Exercise left to you 
)
So the only AND and OR operations to satisfy the equality conditions can be performed on the same number itself. Your subsequences are thus reduced to those having the same number (and its duplicates). Hence, you can simply do the following :
1. Find number of occurrences of each element in the array, store it is OCCURRENCE[i] (corresponding to number i )
2. Find the maximum value of OCCURRENCE[i]*i by scanning through all the array positions.
This maximum value is your answer! 
Once again, note why sub-sequences of duplicates are being made. It is because of the condition that AND of the subsequence should be equal to their OR.
It was an easy one but showed a nice Bit Manipulation property.
You can surely reduce the execution time if you increase the value of array like
VALUE[i] += i;
& then find the max on the spot..
if n is no of elements then
MAX=0;
while(n–)
{
SCAN i;
VALUE[i]+=i;
if(MAX < VALUE[i])
MAX=VALUE[i];
}
Then MAX will contain maximum value with one less loop…
Yes! Absolutely right!
Also, the complexity remains O(n).
But it is better to explain it in this way