温馨提示×

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

小亿
98
2023-10-27 10:35:08
栏目: 编程语言

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

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

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

  1. 如果sum大于等于0,说明前面的连续子数组的和对后面的子数组的和是有贡献的,因此将num加到sum中,并更新maxSum的值。
  2. 如果sum小于0,说明前面的连续子数组的和对后面的子数组的和没有贡献,因此将sum更新为num。
  3. 比较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)的情况下求得连续子数组的最大和。

0