gaoxinbo1984
BAN USERI 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[end1] then recursively call isKPalindrome(s,start+1,end1,k)
else return isKPalindrome(s,start+1,end,k1 )  isKPalindrome(s,start,end1,k1)
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[n1] 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 = i2;
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;
}

gaoxinbo1984
June 25, 2013 It is chinese char.
It means "10 Million entries"
I think a binary search algorithm may solve this problem.
 gaoxinbo1984 October 30, 2013For 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