@@ -0,0 +1,2023 @@
+import java.util.Arrays;%0A%0Apublic class Candy_Greedy %7B%0A%09// faster. two scans from left, then from right%0A    public int candyTwoScanFast(int%5B%5D ratings) %7B%0A        if (ratings == null %7C%7C ratings.length == 0) return 0;%0A        %0A        int len = ratings.length;%0A        int tot = 0;%0A        int%5B%5D candy = new int%5Blen%5D;%0A        Arrays.fill(candy, 1);%0A%0A        %0A        // scan 1, left to right, ascending%0A        for (int i=1; i%3Clen; i++) %7B%0A            if (ratings%5Bi%5D %3E ratings%5Bi-1%5D) %7B%0A                candy%5Bi%5D = candy%5Bi-1%5D + 1;%0A            %7D%0A        %7D%0A        %0A        // scan 2, right to left, descending%0A        for (int i=len-1; i%3E0; i--) %7B%0A            if (ratings%5Bi-1%5D %3E ratings%5Bi%5D && candy%5Bi-1%5D %3C= candy%5Bi%5D) %7B%0A                candy%5Bi-1%5D = candy%5Bi%5D + 1;%0A            %7D%0A        %7D%0A        %0A        for (int tmp : candy) %7B%0A            tot += tmp;%0A        %7D%0A        return tot;%0A    %7D%0A    %0A%09// Greedy, TLE%0A    public int candyGreedySlow(int%5B%5D ratings) %7B%0A        if (ratings == null %7C%7C ratings.length == 0) return 0;%0A        %0A        int len = ratings.length;%0A        int tot = 0;%0A        int%5B%5D candy = new int%5Blen%5D;%0A        candy%5B0%5D = 1;%0A        %0A        for (int i=1; i%3Cratings.length; i++) %7B%0A            if (ratings%5Bi%5D == ratings%5Bi-1%5D) %7B%0A                candy%5Bi%5D = candy%5Bi-1%5D;%0A            %7D else if (ratings%5Bi%5D %3E ratings%5Bi-1%5D) %7B%0A                candy%5Bi%5D = candy%5Bi-1%5D + 1;%0A            %7D else %7B%0A                // update all previous, this takes more time than DP two scans algorithm%0A                candy%5Bi%5D = 1;%0A                if (candy%5Bi-1%5D == 1) %7B  // bump all the previous ones%0A                    for (int j=i-1;j%3E0;j--) %7B%0A                        if (ratings%5Bj%5D %3C ratings%5Bj-1%5D) %7B%0A                            candy%5Bj%5D++;%0A                            candy%5Bj-1%5D++;%0A                        %7D else %7B%0A                            break;%0A                        %7D%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A        %0A        for (int tmp : candy) %7B%0A            tot += tmp;%0A        %7D%0A        return tot;%0A    %7D%0A%7D%0A

add back