algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }