java怎么求连续子数组的最大和-开发者知识库平台

java怎么求连续子数组的最大和

Java

1071

2023/10/1 10:35:08

栏目: 编程语言

要求一个数组的连续子数组的最大和，可以使用动态规划的方法。

假设数组为nums，定义一个变量sum来表示当前连续子数组的和，初始化为0。再定义一个变量maxSum来表示最大和，初始化为数组中第一个元素。

然后遍历数组，对于数组中的每一个元素num：

如果sum大于等于0，说明前面的连续子数组的和对后面的子数组的和是有贡献的，因此将num加到sum中，并更新maxSum的值。
如果sum小于0，说明前面的连续子数组的和对后面的子数组的和没有贡献，因此将sum更新为num。
比较sum和maxSum的值，将较大的值赋给maxSum。

最后，返回maxSum即为连续子数组的最大和。

以下是Java代码实现：

public int maxSubArray(int[] nums) {
    int sum = 0;
    int maxSum = nums[0];
    
    for (int num : nums) {
        if (sum >= 0) {
            sum += num;
        } else {
            sum = num;
        }
        
        maxSum = Math.max(maxSum, sum);
    }
    
    return maxSum;
}

使用该方法，可以在时间复杂度为O(n)的情况下求得连续子数组的最大和。

辰迅云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

java怎么求连续子数组的最大和

最新知识库

相关标签