巨硬面试题:最大子数组

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

样例 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 。

在线做题地址

算法

贪心

算法分析

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

算法步骤

  1. 定义 maxAns 记录全局最大值,即结果; sum 记录当前子数组的和;
  2. 初始化:maxAns=Integer.MIN_VALUE; sum=0;
    因为数组可以全为负数,因此 maxAns 不能直接初始化为 0 ;
  3. 遍历整数数组:
  • Sum 累加当前的值;
  • 若当前 sum>maxAns,更新 maxAns=sum ;
  • 若当前 sum<0,表示当前的子数组和已经为负,累加到后面会使和更小,因此令 sum=0,相当于放弃当前的子数组,重新开始;

复杂度

  • 时间复杂度: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 < nums.length; i++) {
            sum += nums[i];
            maxAns = Math.max(maxAns, sum);
            sum = Math.max(sum, 0);
        }

        return maxAns;
    }
}
有知乎的大佬吗,请问你们禁言算法怎么做的,怎么禁言如此频繁,隔一天禁言我一次

YIFZ:现在我只要在涉及商品下面回答问题,不管我说什么,哪怕文字里什么商品都没有,什么品牌都没有,也照样禁言我,简直没完没了。 你们算法是不是当一个用户被禁言多了,误伤多了,不管申诉成功没,每隔几天禁言一次,一直到账号永久禁言为止。

路由算法

xiaosenlin1:假设有 5000 个小房子 有入口和出口 现在求 某一个入口到某一个出口的 最短 10 条路径有没有大师做过类似的 计算nulI:之前用 pg 库的 pgRouting 做过。或者看下算法里图的那块手写?

咨询:朋友的书法培训一直在几个小学面授,现在想在线网课,学生们可在线购买,能推荐几个在线授课系统吗?

greenthumbers:朋友的书法班(其实就一个知名的书法家)之前在几个小学面授孩子们硬笔书法,现在想开通网课,学生可以在线购买,随时重复观看讨论等,并能售卖一些字帖、文具一类的。 大家有好的网课系统推荐吗?

我一寻思着,互联网的发展是不是更加的财富不均啊?

lysS:信息获取越来越高效和单一,马太效应越来越严重;比如现在的电商,销量几乎都集中在几家手中cccp2020:资本从幼稚走向成熟的一个阶段而已,有没有互联网都会发生这种事情 q8164305:是的,互联网加剧了马太效应 hoyixi:自媒体更是,你发的内容,有几个人看到,完全平台掌控。美其名曰算法推荐,总共就给你几十最多几百播放量,就能据此决定推荐否?搞…

微信订阅号消息打乱了时间线,就是为了投放竞价广告吗

Xillusion:除了打乱时间线,还有在前排永远关不掉的 NC 公众号推荐。我不是产品,就想问问,这种设计应该只是为了赚钱吧,用户体验极差。mercury233:人的阅读能力有限,文章数量过多时肯定要调整排序的,微信的主要问题是算法不行。即使按时间顺序,照样不影响给你插硬广和精选推荐之类的软广。