种花

贪心法

public class Main {
    public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
        int N = sc.nextInt();
        int[] target = new int[N];
        for (int i = 0; i < N; ++i) {
            target[i] = sc.nextInt();
        }
        int cnt = 0;
        for (int i = 1; i < N; ++i) {
            if (target[i - 1] > target[i]) {
                cnt += target[i - 1] - target[i];
            }
        }
        System.out.println(cnt + target[N - 1]);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,x,s=0;
    cin>>n;
    int a[n+1];
    for(int i=0;i<n;i++)
        cin>>a[i];
    a[n] = 0;
    for(int i=0;i<n;i++)
        s += max(0, a[i]-a[i+1]);
    cout<<s<<endl;
    return 0;
}

思路一：递归

n = int(input())
l = list(map(int, input().split()))
res = 0
L = [l]
while len(L) > 0:
    next = []
    for l in L:
        minN = min(l)
        tmp = []
        res += minN
        for e in l:
            if e == minN:
                if len(tmp) != 0:
                    next.append(tmp)
                    tmp = []
            else:
                tmp.append(e-minN)
        if len(tmp) > 0:
            next.append(tmp)
    L = next
print(res)

但是上述解法只能A65%的数据

参考了大佬前排大佬的思路
思路二：贪心
因为相邻的差值是一定需要加到我们最后的结果中的，这里解释一下为什么加上最后一个数，是因为我们在循环中，没有计算最后的花朵的数量，而且最后一个园区的花朵，也必定要种l[-1]天

n = int(input())
l = list(map(int, input().split()))
res = 0
for i in range(n-1):
    res += max(0, l[i] - l[i+1])
print(res + l[-1])

if __name__=='__main__':
    n = int(input())
    num = list(map(int,input().split()))
    count = 0
    for i in range(n-1):
        count += max(num[i]-num[i+1],0)
    print(count+num[-1])

n = int(input())
nums = list(map(int, input().split()))

cnt = 0
for i in range(len(nums) - 1):
    cnt += max(0, nums[i] - nums[i + 1])
cnt += nums[-1]
print(cnt)

def solve(n,nums):
    """
    单调栈
    栈内只存储递增元素
    时间复杂度O(n)
    :param n:
    :param nums:
    :return:
    """
    nums.append(0)
    stack = []
    res = 0
    for i in range(n+1):
        if not stack or stack[-1]<=nums[i]:
            stack.append(nums[i])
        else:
            res += stack[-1]-nums[i]
            while stack and stack[-1]>nums[i]:
                stack.pop()
            stack.append(nums[i])
    print(res)

n = int(input())
nums = [int(x) for x in input().split()]
solve(n,nums)

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	ans := 0
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	for i := 1; i < n; i++ {
		if a[i-1] > a[i] {
			ans += a[i-1] - a[i]
		}
	}
	ans += a[n-1]
	fmt.Println(ans)
}

import java.util.*;

public class Main
{
    public static void main(String args[])
    {
        int n;
        // 动态规划
        // dp[i] 表示种满当前花园需要的天数，p[i] 表示需要种的花的数量
        // p[i] > p[i-1] dp[i] = dp[i-1] + p[i] - p[i-1]
        // p[i] <= p[i-1] dp[i] = dp[i-1]
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] p = new int[n];
        int[] dp = new int[n];
        
        for(int i = 0; i < n; i++)
        {
            int t = sc.nextInt();
            p[i] = t;
            
            if(i == 0)
                dp[0] = p[0];
            else
                dp[i] = p[i] <= p[i-1] ? dp[i-1] : dp[i-1] + p[i] - p[i-1];
        }
        System.out.println(dp[n-1]);
    }
}

import java.util.Scanner;
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner de=new Scanner(System.in);
        while(de.hasNext()){
            int n=de.nextInt();
           
            int[] res=new int[n];
            for(int i=0;i<n;i++){
                res[i]=de.nextInt();
            }
            Stack<Integer> stack=new Stack<>();
            stack.push(res[0]);
            int count=0;
            for(int i=1;i<n;i++){
                while(!stack.isEmpty()&&res[i]<stack.peek()){
                    int d=stack.pop();
                    int d1=res[i];
                    if(!stack.isEmpty()){
                        d1=Math.max(d1,stack.peek());
                    }
                    count+=d-d1;
                }
                    stack.push(res[i]);
                }
            while(!stack.isEmpty()){
                int f=stack.pop();
                if(!stack.isEmpty()){
                    count+=f-stack.peek();
                }else{
                    count+=f;
                }
            }
            System.out.println(count);
            }
        }
    }

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author: coderjjp
 * @Date: 2020-05-11 12:40
 * @Description: 种花
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] line2 = br.readLine().split(" ");
        int A[] = new int[N];
        for (int i = 0; i < N; i++)
            A[i] = Integer.parseInt(line2[i]);
        int cur = 0;
        int ans = 0;
        while (cur < N && A[cur] == 0)//找到第一个不为0
                cur++;
        while (cur < N){
                        //但下面这个循环耗时比较长
            for (int j = cur; j < N && A[j] > 0; j++)//从cur开始向后种，能种的全种上
                A[j]--;
            ans++;//天数加1
            while (cur < N && A[cur] == 0)//种完一遍后从cur向后找到下一个不为0的待种花园
                cur++;
        }//cur = N, 说明已全部种上，跳出循环,贪心法
        System.out.println(ans);
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author: coderjjp
 * @Date: 2020-05-11 13:42
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] line2 = br.readLine().split(" ");
        int A[] = new int[N];
        for (int i = 0; i < N; i++)
            A[i] = Integer.parseInt(line2[i]);
        int dp[] = new int[N];
        dp[0] = A[0];
        for (int i = 1; i < N; i++){
            if (A[i] <= A[i-1])
                dp[i] = dp[i-1];
            else
                dp[i] = dp[i-1] + (A[i] - A[i-1]);
        }
        System.out.println(dp[N-1]);
    }
}