imps
BAN USERIt can be done pretty straightforward. We're basically looking for the point of rotation and the beautiful thing about this case is that one part of the array will always be sorted, given distinct elements.
So we just check if the latter part of the array is sorted, if it's not, we look for the inflection point there and hence the min. If it is, that means that either the inflection point is in the lower part of the array or maybe there's no inflection point at all.
int getMinimum(vector<int> input){
if(!input.size())
return -1;
if(input.size()==1){
return input[0];
}
int start = 0;
int end = input.size()-1;
int mid;
while(start <= end){
mid = start + (end-start)/2;
if(start==end){
return input[start];
}
if(input[mid] > input[end]){
start = mid+1;
} else {
end = mid;
}
}
}
Here you're just assuming substitution.
However, insertion and deletion also render a string to be 1-edit distance away.
There's really no better than O(n*m) if we want to calculate the exact distance. And mine is actually very inefficient cause I'm just using plain recusion rather than DP. But it works, it's simple enough to deliver the idea.
This is called levenshtein distance.
int LevenshteinDistance(string s, string t){
if(s.size()==0)
return t.size();
if(t.size()==0)
return s.size();
// check last char
int cost;
if (s[s.size()-1] == t[t.size()-1])
cost = 0;
else
cost = 1;
// minimum deleting char from s, from t and from both
return minimum(LevenshteinDistance(s.substr(0,s.size()-1),t) + 1,
LevenshteinDistance(s,t.substr(0,t.size()-1)) + 1,
LevenshteinDistance(s.substr(0,s.size()-1),t.substr(t.size()-1)) + cost);
}
Since we're looking for a subarray with positive numbers we can easily do this in linear time.
This should cover all the border cases:
1. If the number is negative, reset the counters
2. If the number is positive, update the current counter and if need be update the max.
pair<int,int> maxContinuousSubarray(vector<int> v){
if(v.size()==0)
return make_pair(-1,-1);
int maxSoFar = 0, maxCur = 0;
int maxStart = -1, maxEnd = -1;
int maxStartCurrent = 0;
for(int i = 0; i < v.size(); i++){
if(v[i] < 0){
maxStartCurrent = i+1;
maxCur = 0;
} else {
maxCur+=v[i];
if(maxCur > maxSoFar){
maxStart = maxStartCurrent;
maxEnd = i;
maxSoFar = maxCur;
}
}
}
return make_pair(maxStart,maxEnd);
}
Try sort and sort1...your algorithm will assume there's no difference between the 2.
- imps November 24, 2014