牛客NC406 最长山脉【中等穷举，动态规划 C++/Java/Go/PHP】

本文主要是介绍牛客NC406 最长山脉【中等穷举，动态规划 C++/Java/Go/PHP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/f4e974a50eda429fbf36515a4197b148

思路

在这里插入图片描述

参考答案C++

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型vector* @return int整型*/int longestmountain(vector<int>& nums) {//枚举每个山顶，动态规划if (nums.size() < 3) return 0;int n = nums.size();int left[n];int right[n];for (int i = 0; i < n; i++) {left[i] = 1;if (i > 0 && nums[i] > nums[i - 1]) {left[i] = left[i - 1] + 1;}}for (int i = n - 1; i >= 0; i--) {right[i] = 1;if (i < n - 2 && nums[i] > nums[i + 1]) {right[i] = right[i + 1] + 1;}}int ans = 0;for (int i = 0; i < n; i++) {if (left[i] > 1 && right[i] > 1) {int cur = left[i] + right[i] - 1;if (cur > ans) {ans = cur;}}}return ans;}
};

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型ArrayList* @return int整型*/public int longestmountain (ArrayList<Integer> nums) {//枚举每个山顶，动态规划if (nums == null || nums.size() < 3) return 0;int n = nums.size();int[] left = new int[n];int[] right = new int[n];for (int i = 0; i < n; i++) {left[i] = 1;if (i > 0 && nums.get(i) > nums.get(i - 1)) {left[i] = left[i - 1] + 1;}}for (int i = n - 1; i >= 0 ; i--) {right[i] = 1;if (i < n - 2 && nums.get(i) > nums.get(i + 1)) {right[i] = right[i + 1] + 1;}}int ans = 0x80000000;for (int i = 0; i < n ; i++) {if (left[i] > 1 && right[i] > 1) {int cur = right[i] + left[i] - 1;if (cur > ans) {ans = cur;}}}if (ans == 0x80000000) return 0;return ans;}
}

参考答案Go

package main//import "fmt"/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @return int整型*/
func longestmountain(nums []int) int {//枚举每个山顶，动态规划if nums == nil || len(nums) < 3 {return 0}n := len(nums)left := make([]int, n)right := make([]int, n)for i := 0; i < n; i++ {left[i] = 1if i > 0 && nums[i] > nums[i-1] {left[i] = left[i-1] + 1}}for i := n - 1; i >= 0; i-- {right[i] = 1if i < n-2 && nums[i] > nums[i+1] {right[i] = right[i+1] + 1}}ans := 0for i := 0; i < n; i++ {if left[i] > 1 && right[i] > 1 {cur := left[i] + right[i] - 1if cur > ans {ans = cur}}}return ans
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型*/
function longestmountain( $nums )
{//枚举每个山顶，动态规划if($nums ==null || count($nums) <3)return 0;$n  = count($nums);$left = [];$right=[];for($i=0;$i<$n;$i++){$left[$i] =1;if($i>0 && $nums[$i] > $nums[$i-1]){$left[$i] = $left[$i-1]+1;}}for($i=$n-1;$i>=0;$i--){$right[$i] =1;if($i<$n-2 && $nums[$i]>$nums[$i+1]){$right[$i]=$right[$i+1]+1;}}$ans = 0;for($i=0;$i<$n;$i++){if($left[$i] >1 && $right[$i] >1) {$cur = $left[$i]+$right[$i]-1;if($cur > $ans){$ans = $cur;}}}return $ans;
}