最大上升子阵列总和-php教程-PHP中文网

最大上升子阵列总和

碧海醫心

发布： 2025-02-05 08:52:01

原创

755人浏览过

最大上升子阵列总和

题目：最大上升子数组和

难度：简单

主题：数组

给定一个正整数数组，求其最大上升子数组的和。上升子数组定义为数组中连续的一段数字，且每个数字都严格大于前一个数字。长度为1的子数组也被认为是上升的。

示例1：

输入：nums = [10,20,30,5,10,50] 输出：65 说明：[5,10,50] 是一个上升子数组，其和为 65，是所有上升子数组中最大的。

示例2：

输入：nums = [10,20,30,40,50] 输出：150 说明：[10,20,30,40,50] 是一个上升子数组，其和为 150。

示例3：

输入：nums = [12,17,15,13,10,11,12] 输出：33 说明：[10,11,12] 是一个上升子数组，其和为 33。

约束：

1 ≤ nums.length ≤ 10⁵ 1 ≤ nums[i] ≤ 10⁴

解题思路：

我们可以使用动态规划的思想来解决这个问题。我们用 current_sum 变量记录当前上升子数组的和，用 max_sum 变量记录到目前为止遇到的最大上升子数组的和。

遍历数组，对于每个元素：

如果该元素大于前一个元素，则将其添加到 current_sum 中。
如果该元素小于或等于前一个元素，则说明当前上升子数组结束，将 current_sum 与 max_sum 比较，更新 max_sum，并将 current_sum 重置为当前元素的值。

最后，返回 max_sum。

PHP 代码：

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function maxAscendingSum(array $nums): int {
    $max_sum = $nums[0];
    $current_sum = $nums[0];

    for ($i = 1; $i < count($nums); $i++) {
        if ($nums[$i] > $nums[$i - 1]) {
            $current_sum += $nums[$i];
        } else {
            $max_sum = max($max_sum, $current_sum);
            $current_sum = $nums[$i];
        }
    }

    return max($max_sum, $current_sum);
}

// Example usage:
$nums1 = [10,20,30,5,10,50];
$nums2 = [10,20,30,40,50];
$nums3 = [12,17,15,13,10,11,12];

echo maxAscendingSum($nums1) . "\n"; // Output: 65
echo maxAscendingSum($nums2) . "\n"; // Output: 150
echo maxAscendingSum($nums3) . "\n"; // Output: 33
?>

登录后复制

时间复杂度：O(n)

空间复杂度：O(1)

这个解法简洁高效，能够处理各种情况，包括只有一个元素的数组和所有元素都递减的数组。代码中添加了更清晰的注释，并使用了更具描述性的变量名。

以上就是最大上升子阵列总和的详细内容，更多请关注php中文网其它相关文章！