剑指offer面试题[31]-连续数组的最大和

我不是女神ヾ 2022-06-12 14:39 116阅读 0赞

## 题目描述 ##

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:\{6,-3,-2,7,-15,1,2,2\},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)

//方法1：应用动态规划法
    class Solution {
    public:
        int FindGreatestSumOfSubArray(vector<int> array) {
            int maxValue=0x80000000;
            int sum=0;
            for(int i=0;i<array.size();i++)
              {
                sum=max(array[i],sum+array[i]);
                maxValue=max(sum,maxValue);
              }
            return maxValue;
        }
    };
    
    /*方法2：举例分析数组的规律
    class Solution {
    public:
        int FindGreatestSumOfSubArray(vector<int> array) {
           int len=array.size();
           int maxValue=0x80000000;
           int sum=0;
           for(int i=0;i<len;i++)
             {
                if(sum<=0)
                    sum=array[i];
                else
                    sum+=array[i];
                if(sum>maxValue)
                    maxValue=sum;
             }
           return maxValue;
        }
    };
    */

发表评论取消回复

表情：

评论列表（有 0 条评论，116人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer-Java版】31连续子数组的最大和

连续子数组最大和，要求O(n)时间复杂度思路：核心思想就是当前遍历数组的时候，遇到的是一个正数，计算这个正数加上已有的和得到一个新的和如果这个新的和比当前的正数大，那

左手的ㄟ右手/ 2022年08月21日 09:48/ 0 赞/ 110 阅读

相关剑指offer：连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正

╰半橙微兮°/ 2022年08月05日 08:58/ 0 赞/ 171 阅读

相关剑指offer之面试题31连续子数组的最大和

问题描述：输入一个整形数组，数组里有正数也有负数。数组中一个或者连续的多个数组组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。实现代码如下：

深碍√TFBOYSˉ_/ 2022年07月24日 04:03/ 0 赞/ 146 阅读

相关剑指offer面试题[31]-连续数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候

我不是女神ヾ/ 2022年06月12日 14:39/ 0 赞/ 117 阅读

相关【剑指offer】面试题42：连续子数组的最大和

题目输入一个整形数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如，输入的数组为\{1

心已赠人/ 2022年06月11日 04:44/ 0 赞/ 160 阅读

相关剑指offer-题31：连续子数组的最大和

题目描述输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如：输入数组为\{

刺骨的言语ヽ痛彻心扉/ 2022年05月28日 09:21/ 0 赞/ 117 阅读

相关【剑指offer】面试题42：连续子数组的最大和

> 题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。牛客网链接：[https:/

秒速五厘米/ 2022年04月22日 15:16/ 0 赞/ 173 阅读

相关【剑指Offer】（数组）连续子数组的最大和

题目链接：[https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&tqId=11

「爱情、让人受尽委屈。」/ 2022年03月16日 12:48/ 0 赞/ 204 阅读

相关 31. 连续子数组的最大和《剑指Offer》(Java版)

题目描述 > 给一个数组，返回它的最大连续子序列的和，例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。

拼搏现实的明天。/ 2022年01月30日 11:27/ 0 赞/ 170 阅读

相关剑指offer：连续子数组的最大和

试题： HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问

柔光的暖阳◎/ 2021年06月24日 16:09/ 0 赞/ 383 阅读