分糖果问题

题目链接：https://www.nowcoder.com/practice/76039109dd0b47e994c08d8319faa352

题目描述

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

1. 每个孩子不管得分多少，起码分到一个糖果。

2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组 arr 代表得分数组，请返回最少需要多少糖果。

要求: 时间复杂度为 O(n) 空间复杂度为 O(n)

数据范围： 1 ≤ n ≤ 100000 ，1 ≤ ai ≤ 1000

示例 1：

输入：   [1,1,2]
返回值： 4
说明：   最优分配方案为1,1,2

示例 2：

输入：   [1,1,1]
返回值： 3
说明：   最优分配方案是1,1,1

解题代码

import java.util.*;

public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int N = arr.length;
        if (N == 1) {
            return 1;
        }
        int[] dp = new int[N];
        Arrays.fill(dp, 1);
        for (int i = 1; i < N; i++) {
            if (arr[i - 1] < arr[i]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        int ans = dp[N - 1];
        for (int i = N - 2; i > -1; i--) {
            if (arr[i] > arr[i + 1] && dp[i] <= dp[i + 1]) {
                dp[i] = dp[i + 1] + 1;
            }
            ans += dp[i];
        }
        return ans;
    }
}