jarc
BAN USERdouble getMax(vector< pair<double, double> > v) {
assert(v.size() > 0);
int bleft=0, bright=0;
int tmp_left = 0;
double bv=v[0].second;
double cv = bv;
for (int i = 1; i < v.size(); i++) {
if (cv < 0 || v[i].first < v[i-1].first) {
cv = v[i].second;
tmp_left = i;
} else {
cv += v[i].second;
}
if (bv < cv) {
bleft = tmp_left;
bright = i;
bv = cv;
}
}
return bv;
}
A greedy method should be OK, I think. The C++ code:
bool myCmp(string S, string T) {
int lenS = S.length();
int lenT = T.length();
for (int i = 0, j = 0; i < lenS, j < lenT; j++) {
if (S[i] == T[j]) i++;
}
return i == lenS ? true : false;
}
The space complexity is O(1); The time complexity is O(n), where n = length of T.
Please correct me, if it's wrong.
Sorry, I was wrong. But how about this input :
- jarc November 19, 2013(1, 2) (2, -100) (3, 3) (4, 4) (5,5)
Your output will be : 2.
But the best should be : 3 + 4 + 5. right?
Note that 'start' in your code will always be 0.