Leetcode 135: Candy (O(n) 2 vectors)

leetcode_135b.cpp

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int candy(vector<int>& ratings) {
    vector<int> left(ratings.size(), 1);
    vector<int> right(ratings.size(), 1);
    for (int i=1; i<left.size(); ++i) {
        if (ratings[i]>ratings[i-1]) left[i] = left[i-1] + 1;
        else left[i] = 1;
    }
    for (int i=right.size()-2; i>=0; --i) {
        if (ratings[i]>ratings[i+1]) right[i] = right[i+1] + 1;
        else right[i] = 1;
    }
    int sum = 0;
    for (int i=0; i<left.size(); ++i) sum += max(left[i], right[i]);
    return sum;
}

int main() {
    vector<int> ratings {1,4,3,2,4,6,3}; //{1,0,2};
    cout << candy(ratings) << "\n";
    return 0;
}