CareerCup

I think a binary search algorithm may solve this problem.
For example, the input array is 1 3 7 9 11
start = 0
end = len(A)
while(start<end)
if A[mid] == mid*2+1
start = mid+1
if A[mid] > mid*2+1
end = mid

return start*2+1

I think this question can be solve by following idea.
I define the function like this :
bool isKPalindrom(string s, int start, int end, int k)

The input is string s , its begin position, its end position and k.

If s[start:end] is palindrome then return true
else
if k < 0 return false
else if s[start] == s[end-1] then recursively call isKPalindrome(s,start+1,end-1,k)
else return isKPalindrome(s,start+1,end,k-1 ) || isKPalindrome(s,start,end-1,k-1)

We can also use a array to record the result of whether s[start,end] is palindrome

The time complxity is (n^2)

it is 3 sum problem.
first of all, sort the array,
then for each array[i], it is our job to find two elements from array[i+1] to array[n-1] that their sum is 0.
then this question becomes 2sum problem.

if the array is unique the time complexity is O(n^2)
if the array has replicated elements, time complexity is O(n^2log(n))

I think this question can be solved by one pass traversal.
Use an additional array sum which sum[i] represents sum from data[0] to data[i].
If we find two elements in array sum that they have the same value, for example, sum[i] = sum[j]
then we can sure that the sum of continuous sequence data[i+1] to data[j] is zero.
Note that there maybe an exception. If any sum[i]`s value is zero, that means the sum of sequence from data[0] to data[i] is zero

For example
input is -1, -3, 4, 5, 4
sum is -1, -4, 0, 5,9
sum[2] is zero that means data[0] + data[1] + data[2] = 0

input is 1,3,5,7,9,-2,2
sum is 1 4 9 16 25 23 25
sum[4] = sum[6], that means data[5] + data[6] = 0

Time complexity is O(n)
Space complexity is O(n)

int count2(const vector<int> & vec ){
    if(vec.size() == 0)
        return 0;
    else if(vec.size() == 1){
        return vec[0] >0 ? vec[0] : 0;
    }
    else if(vec.size() == 2){
        int result = vec[0] > vec[1] ? vec[0] : vec[1];
        if(result > 0)
            return result;
        else
            return 0;
    }

    int max = vec[0] > 0 ? vec[0] : 0;
    int result = INT_MIN;
    vector<int> d(vec.size());
    d[0] = vec[0] >0 ? vec[0] : 0;
    d[1] = vec[0] > vec[1] ? vec[0] : vec[1];

    for(int i=2;i<vec.size();i++){
        int t = i-2;
        if(max < d[t])
            max = d[t];
        if(vec[i]>0)
            d[i] = vec[i] + max;
        else
            d[i] = max;
    }

    for(int i=0;i<d.size();i++){

        if(result < d[i])
            result = d[i];
    }

    return result;
}

It is chinese char.
It means "10 Million entries"