当前位置: 面试刷题>> 最大子数组差 (经典算法题500道)


题目描述补充

题目:最大子数组差

给定一个整数数组 nums,你需要找到该数组中的一个子数组(连续的元素序列),使得该子数组的最大值与最小值之差尽可能大。返回这个最大差值。

示例 1:

输入: nums = [5, 2, 9, 1]
输出: 7
解释: 子数组 [5, 2, 9] 的最大值为 9,最小值为 2,差值为 9 - 2 = 7。

示例 2:

输入: nums = [1, 3, 5, 4, 2, 8, 6, 7]
输出: 6
解释: 子数组 [3, 5, 4, 2, 8] 的最大值为 8,最小值为 2,差值为 8 - 2 = 6。

注意

  • 数组长度在 [2, 10^5] 范围内。
  • 数组中的元素在 [-10^9, 10^9] 范围内。

PHP 示例代码

function maximumSubarrayDifference($nums) {
    $n = count($nums);
    $maxDiff = PHP_INT_MIN;
    $currentMin = PHP_INT_MAX;
    $currentMax = PHP_INT_MIN;
    $currentDiff = 0;

    for ($i = 0; $i < $n; $i++) {
        $currentMin = min($currentMin, $nums[$i]);
        $currentMax = max($currentMax, $nums[$i]);
        $currentDiff = max($currentDiff, $currentMax - $currentMin);
        
        // 如果当前最大值减去当前最小值小于等于之前计算的最大差值,
        // 则考虑以当前元素为新的子数组起点,重置当前最小值和最大值
        if ($nums[$i] - $currentMin >= $currentDiff) {
            $currentMin = $nums[$i];
            $currentMax = $nums[$i];
        }

        $maxDiff = max($maxDiff, $currentDiff);
    }

    return $maxDiff;
}

// 示例
$nums = [5, 2, 9, 1];
echo maximumSubarrayDifference($nums);  // 输出 7

Python 示例代码

def maximumSubarrayDifference(nums):
    max_diff = float('-inf')
    current_min = float('inf')
    current_max = float('-inf')
    current_diff = 0

    for num in nums:
        current_min = min(current_min, num)
        current_max = max(current_max, num)
        current_diff = max(current_diff, current_max - current_min)

        # 优化:如果当前元素减去当前最小值大于等于当前差值,则重置当前最小值和最大值
        if num - current_min >= current_diff:
            current_min = num
            current_max = num

        max_diff = max(max_diff, current_diff)

    return max_diff

# 示例
nums = [5, 2, 9, 1]
print(maximumSubarrayDifference(nums))  # 输出 7

JavaScript 示例代码

function maximumSubarrayDifference(nums) {
    let maxDiff = -Infinity;
    let currentMin = Infinity;
    let currentMax = -Infinity;
    let currentDiff = 0;

    for (let num of nums) {
        currentMin = Math.min(currentMin, num);
        currentMax = Math.max(currentMax, num);
        currentDiff = Math.max(currentDiff, currentMax - currentMin);

        // 优化:如果当前元素减去当前最小值大于等于当前差值,则重置当前最小值和最大值
        if (num - currentMin >= currentDiff) {
            currentMin = num;
            currentMax = num;
        }

        maxDiff = Math.max(maxDiff, currentDiff);
    }

    return maxDiff;
}

// 示例
const nums = [5, 2, 9, 1];
console.log(maximumSubarrayDifference(nums));  // 输出 7

码小课网站中有更多相关内容分享给大家学习,包括算法基础、数据结构、面试技巧等,欢迎访问学习。

推荐面试题