53. 最大子序和

x33g5p2x  于12个月前 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(89)

最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

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

解题思路

说实话,一开始拿到这道题目还真不知道如何下手。但是有一种暴力的方法肯定可以,就是遍历呗谁不会呢。也就是正着思考,按个暴力遍历,看看以第i个元素开头的最大子序列是多少。可以是可以,但是效率肯定低压
想着想着不知不觉间想到了具体数学里面的一些思考方式。我们可以先拿小的来进行实验,观察他们直接的关系
假设只有一个元素,肯定结果就是那一个元素,如果是两个以及上呢?
假设有n个我们可以从头到尾依次增加,下面表示序列长度
1
2
3
4

n-1
n
我们用一个变量max来存储,最大子序和。
首先,max肯定等于第一个元素呀。因为只有一个嘛
当二个的时候,有三种情况,第一个元素是最大子序和,第二个元素是最大子序和或者两元素之和为最大子序和。第一个元素我们已经用max存储起来了。下面只需要将第二个元素与两元素之和比较过后的最大值与max进行比较即可。

思考一下我们会发现,以第i个数为结尾的子序和中的最大值,无非就第i个数自己 或者 以第i-i个数结尾的子序和中的最大值和第i个数的和

例如:
[-2 , 1, -3, 4, -1, 2, 1, -5, 4]
从第0个到最后一个以第i个元素结尾的最大子序和为://-2 -1 -3 4 3 5 6 1 5 //, 其中的最大值6,就是整个序列的最大子序和。
思考道这里我们是不是就会发现,将数组遍历过后,以第i个数结尾的子序和的最大值,中的最大值就是我们整个序列的最大子序和。

代码实现

  • 1
class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int max;
        for(int i = 0; i < nums.length; i++){
            int sum = 0;
            max = nums[i];
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                max = max>sum?max:sum;
            }
            ans = ans>max ?ans:max;
        }
        return ans;
    }
}

在这里插入图片描述

  • 2
class Solution {
    public int maxSubArray(int[] nums) {
        int last = 0, Ans = nums[0];
        for (int i : nums) {
            last = Math.max(last + i, i);
            Ans = Math.max(Ans, last);
        }
        return Ans;
    }
}

在这里插入图片描述