7月23日:小红书提前批笔试第三题
没投小红书提前批,下来做了下第三题(第一题签到题;第二题没看,大家说看不懂题意),时间复杂度 O(n),塔子哥 OJ 上提交 AC
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int t = cin.nextInt(); while (t-- > 0) { int n = cin.nextInt(); long v = cin.nextLong(); long[] nums = new long[n]; for (int i = 0; i < n; i++) { nums[i] = cin.nextLong(); } // dp[0][j]: 不强化 nums[0] ~ nums[j] 的子序和 // dp[1][j]: 强化 nums[0] ~ nums[j] 中的某一个的子序和,又分为强化 nums[j] 和 不强化 nums[j] long[][] dp = new long[2][n]; dp[0][0] = nums[0]; dp[1][0] = v; long maxSum = Math.max(dp[0][0], dp[1][0]); for (int j = 1; j < n; j++) { // 不强化时 nums[0] ~ nums[j] 的子序和 dp[0][j] = Math.max(dp[0][j - 1] + nums[j], nums[j]); // 强化 nums[j]:Math.max(dp[0][j - 1] + v, v) // 不强化 nums[j],强化 nums[0] ~ nums[j-1] 中的某一个,即 dp[1][j - 1]:dp[1][j - 1] + nums[j] dp[1][j] = Math.max(Math.max(dp[0][j - 1] + v, v), dp[1][j - 1] + nums[j]); maxSum = Math.max(maxSum, Math.max(dp[0][j], dp[1][j])); } System.out.println(maxSum); } } }#提前批简历挂麻了怎么办##小红书信息集散地#