【LeetCode/LintCode】阿里巴巴面试高频题：最大子数组

2021-03-27 03:25

阅读：675

标签：表示复杂度变量 min 九章算法分析 node 放弃 div

给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。

样例1:

输入：[−2,2,−3,4,−1,2,1,−5,3]
输出：6
解释：符合要求的子数组为[4,−1,2,1]，其最大和为 6。

样例2:

输入：[1,2,3,4]
输出：10
解释：符合要求的子数组为[1,2,3,4]，其最大和为 10。

在线评测地址：

LintCode 领扣?

算法

贪心

算法分析

题目要求给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。若直接暴力枚举子数组，时间复杂度需要 O(N2)；
由于题目要求是子数组最大和，因此可以利用贪心思想，通过局部的子数组最大，进而得到整体的最优解；
需要注意贪心的策略不能有后效性；

算法步骤

定义 maxAns 记录全局最大值，即结果；sum 记录当前子数组的和；
初始化： maxAns=Integer.MIN_VALUE; sum=0;

因为数组可以全为负数，因此maxAns不能直接初始化为0；

遍历整数数组：

Sum 累加当前的值；
若当前 sum>maxAns ，更新 maxAns=sum；
若当前 sum

复杂度

时间复杂度：O(N),N为数组长度

只需要遍历一遍数组就能找到答案；

空间复杂度：O(1)

只需要用到maxAns和sum两个变量.

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {

        // maxAns记录全局最大值 sum记录当前子数组的和
        int maxAns = Integer.MIN_VALUE, sum = 0;
        // 贪心
        for (int i = 0; i

更多题解参考：九章算法官网

【LeetCode/LintCode】阿里巴巴面试高频题：最大子数组

标签：表示复杂度变量 min 九章算法分析 node 放弃 div

原文地址：https://www.cnblogs.com/lintcode/p/13674564.html

上一篇：2020年9月15日线程通信问题（面试题）

下一篇：Java面试考点

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【LeetCode/LintCode】阿里巴巴面试高频题：最大子数组
文章链接：http://soscw.com/index.php/essay/68396.html

亲，登录后才可以留言！

【LeetCode/LintCode】阿里巴巴面试高频题：最大子数组

算法

评论

热门文章

推荐文章

最新文章

置顶文章