Java教程

剑指 Offer 42. 连续子数组的最大和

本文主要是介绍剑指 Offer 42. 连续子数组的最大和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

话不多说,先上题目

输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

来源:力扣(LeetCode)

法一

暴力解法:穷举

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int r = 0;
        boolean flag = false;
        for(int i=0;i<nums.length;i++) {
            for(int j=i;j<nums.length;j++) {
                r += nums[j];
                if (r>max) {
                    max = r;
                }
            }
            r=0;
        }
        return max;
    }
}

法二

动态规划

据说是动态规划的最简单的题了,在此学习记录一下

class Solution {
    public int maxSubArray(int[] nums) {
        # 存储以当前下标之前的所有子数组的和的最大值
        int[] arr = new int[nums.length];
        arr[0] = nums[0];
        int max = arr[0];
        for(int i=1;i < nums.length;i++) {
            # 判断当前下标(不包含当前下标)之前所有子数组和的最大值是否为正值
            if(arr[i-1] > 0) {
                # 如果为正值,则将当前值加上
                arr[i] = arr[i-1] + nums[i];
            } else {
                # 如果为负值,则当前下标(包含)之前子数组和的最大值为当前下标对应的值
                arr[i] = nums[i];
            }
            # 然后与保存的最大值比较
            max = Math.max(max, arr[i]);
        }
        return max;
    }
}

image

这篇关于剑指 Offer 42. 连续子数组的最大和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!