Java 中的优质子数组最大分数

任务是给定一个整数 k 和一个整数数组 nums，确定“好”子数组的最大分数。子数组的分数由其长度 (j - i + 1) 乘以其中的最小值确定。子数组的开始和结束索引 (i, j) 定义了子数组。如果索引 k 存在于子数组中，则认为它“好”；因此，i <= k <= j。问题在于找到任何“好”子数组可能获得的最高分数。为了解决这个问题，我们必须快速识别包含 k 且分数高的子数组，这些分数由子数组的最小元素乘以其长度来确定。

子数组 (i, j) 的分数可以表示为 min(nums[i], nums[i+1],..., nums[j]) * (j - i + 1)。当 i <= k <= j 时，子数组被认为是优秀的。

返回一个“好”子数组可以获得的最大分数。

示例 1

输入

int n = [1, 4, 3, 7, 4, 5]

int k = 3

输出

 
The Maximum Score of a Good Subarray is 15   

解释

理想子数组是 (1, 5)，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15。

示例 2

输入

int n = [5, 5, 4, 5, 4, 1, 1, 1]

int k = 0

输出

 
The Maximum Score of a Good Subarray is 20   

解释：理想子数组是 (0, 4)，分数为 min(5, 5, 4, 5, 4) * (4 - 0 + 1) = 4 * 5 = 20。

双指针方法

算法

步骤 1：将最小值变量 mini 和结果变量 res 的值设置为索引 k 处的值。最初，k 应被用作子数组的中心点。

步骤 2：将两个指针 I 和 j 的初始值设置为 k。这两个指针将用于扩展子数组。

步骤 3：只要其中一个指针（I 或 j）没有到达数组的边界。

步骤 3.1：如果 I 在左边界 (0)。

步骤 3.2：如果 j 在右边界 (n - 1)。

步骤 3.3：要将子数组向右扩展，如果 Array[I - 1] 的元素小于 Array[j + 1] 的元素，则增加 j。

步骤 3.4：否则，减少 I 以便向左扩展子数组。

步骤 4：将 A[i] 和 A[j] 之间的最小值添加到 mini。

步骤 5：更新 res，包含 mini * (j - I + 1) 和现有 res 的最大值。这是一个关键步骤，因为它确定了当前子数组的分数，并记录了已发现的最高分数。

步骤 6：继续，直到其中一个箭头越过边界。

步骤 7：最后一步，返回 res 作为优质子数组可能获得的最大分数。

实施

文件名：MaxiScore.java

输出

 
The Maximum Score of a Good Subarray is: 15