Candy Solutions in C++

// Source : https://oj.leetcode.com/problems/candy/
// Author : Hao Chen
// Date   : 2014-10-12



#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <vector>
using namespace std;


void print(vector<int> &v);

/*
 *    The soluiton is O(2n) run-time complexity
 *
 *    For example:
 *
 *        ratings[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 } 
 *
 *    1) Go through the ratings from left to right.
 *
 *       Find the each increasing sub-array, giving the minimal candy     
 *
 *        ratings[] = { 5, 6, 7,   4,   1, 2, 3,   2,   1, 7 } 
 *                      ------>    ->   ------>    ->   --->
 *          candy[] = { 1, 2, 3,   1,   1, 2, 3,   1,   1, 2 }
 *
 *    2) Go through the raings from right to left.
 *
 *             ratings[] = { 5,   6,   7, 4, 1,   2,   3, 2, 1,   7 } 
 *                           <-   <-   <------    <-   <------    <-
 *          prev_candy[] = { 1,   2,   3, 1, 1,   2,   3, 1, 1,   2 }
 *                                        +1              +1
 *               candy[] = { 1,   2,   3, 2, 1,   2,   3, 2, 1,   2 }
 *
 *    3) total candy is 19
 *
 */
int candy(vector<int> &ratings) {

    vector<int> candyCnt(ratings.size()) ;
    //allocate candies, considering the minimal rating on the left
    candyCnt[0] = 1;
    for(int i = 1; i < ratings.size(); i++){
        candyCnt[i] = ratings[i] > ratings[i-1] ? candyCnt[i-1]+1 : 1;
    }
    print(candyCnt); 
    //modify the allocation, considering the minimal rating on the right
    int totalCandy = candyCnt[ratings.size()-1];
    for(int i = ratings.size()-2; i >= 0; i--){
        candyCnt[i] = (ratings[i] > ratings[i+1] && candyCnt[i+1]+1 > candyCnt[i]) ? candyCnt[i+1]+1 : candyCnt[i];
        //count total candies by the way
        totalCandy += candyCnt[i];
    }
    print(candyCnt);
    return totalCandy;
}

void generateRatings(vector<int> &ratings, int n) {
    srand(time(0));
    for (int i=0; i<n; i++) {
        ratings.push_back(rand()%10);
    }
}

void print(vector<int> &v) {
    for(int i=0; i<v.size(); i++){
        cout << v[i] << " ";
    }
    cout << endl;
}

int main(int argc, char**argv)
{
    int n = 10;
    if (argc>1){
        n = atoi(argv[1]);
    }   
    vector<int> ratings;
    generateRatings(ratings, n);
    print(ratings);

    cout << candy(ratings) << endl;

    cout << "--------------------" << endl;
    int r[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 };
    vector<int> ra(r, r+sizeof(r)/sizeof(r[0]));
    print(ra);
    cout << candy(ra) << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/candy/
/// Author : liuyubobobo
/// Time   : 2018-12-10

#include <iostream>
#include <vector>

using namespace std;


/// Two arrays
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int candy(vector<int>& ratings) {

        int n = ratings.size();

        vector<int> left(n, 1);
        for(int i = 1; i < n; i ++)
            if(ratings[i] > ratings[i - 1])
                left[i] = left[i - 1] + 1;

        vector<int> right(n, 1);
        for(int i = n - 2; i >= 0; i --)
            if(ratings[i] > ratings[i + 1])
                right[i] = right[i + 1] + 1;

        int res = 0;
        for(int i = 0; i < n; i ++)
            res += max(left[i], right[i]);
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/candy/
/// Author : liuyubobobo
/// Time   : 2018-12-10

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

using namespace std;


/// Two arrays's thinking
/// But only use one array :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int candy(vector<int>& ratings) {

        int n = ratings.size();

        vector<int> res(n, 1);
        for(int i = 1; i < n; i ++)
            if(ratings[i] > ratings[i - 1])
                res[i] = res[i - 1] + 1;

        for(int i = n - 2; i >= 0; i --)
            if(ratings[i] > ratings[i + 1] && res[i] <= res[i + 1])
                res[i] = res[i + 1] + 1;

        return accumulate(res.begin(), res.end(), 0);
    }
};


int main() {

    return 0;
}