incorrect-greedy.cpp (1058B)
1 #include <vector> 2 #include <iostream> 3 4 using namespace std; 5 6 long long solve(vector<int>& ls) { 7 long long res = 0; 8 int lc = 0; 9 for(int i = 0; i < ls.size(); ++i) { 10 if(ls[i] < 0) { 11 break; 12 } 13 res += ls[i]; 14 lc += 1; 15 } 16 17 int rc = 0; 18 for(int i = ls.size() - 1; i >= 0; --i) { 19 if(!(ls[i] < 0)) { 20 break; 21 } 22 res += ls[i] * -1; 23 rc += 1; 24 } 25 26 // that's not right because some of the innermost elements should be taken in certain cases 27 int left = 0; 28 int right = 0; 29 30 if(lc + rc != ls.size()) { 31 left = abs(ls[lc]); 32 right = abs(ls[(ls.size() - 1) - lc]); 33 } 34 35 return res + max(left,right); 36 } 37 38 int main() { 39 int testCases, len, current = 0; 40 cin >> testCases; 41 for(int z = 0; z < testCases; ++z) { 42 43 cin >> len; 44 vector<int> ls {}; 45 46 for(int i = 0; i < len; ++i) { 47 cin >> current; 48 ls.push_back(current); 49 } 50 51 cout << solve(ls) << endl; 52 } 53 }