Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int Solution::candy(vector<int> &A) {
- int n = A.size();
- int ans = 1;
- if(!n) return 0;
- vector<int> inc(n); inc[0] = 0;
- vector<int> curr(n); curr[0] = 1;
- for(int i = 1; i < n; i++){
- if(A[i] >= A[i-1]) inc[i] = 0;
- else inc[i] = inc[i - 1] + 1;
- }
- for(int i = 1; i < n; i++){
- int last = curr[i - 1];
- if(A[i] > A[i - 1]){
- curr[i] = last + 1;
- ans += curr[i];
- } else{
- ans++;
- if(last == 1){
- // Adding 1 to each one behind me
- // Example : 4 3 2 1 1 <- me
- // Since the last one is 1 and me is also 1, I need to add one to it
- // becomes 2, but the last of the last could be 2 and so on
- // so inc[i] will store how many in incresing order from right to left
- // I have so then I will increment all of them in O(1)
- ans += inc[i];
- // This is a tricky if for a special case
- // Exmaple : 1 2 3 4 5 6 3 2 1 1 <- me
- // With inc[i] I would add 1 to all my last 4 numbers, since I had
- // 6 3 2 1 1 to become 7 4 3 2 1 <- me, but I didnt had to inc
- // 6 to become 7 because 3 + 1 < 6, so I check if my last element of that
- // sequence is greater than the value that it should be, to uncount that
- if(curr[i - inc[i]] > inc[i]) ans--;
- }
- curr[i] = 1;
- }
- }
- return ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement