美文网首页面了个试
求子数组的最大和(微软面试100题003)

求子数组的最大和(微软面试100题003)

作者: Stansosleepy | 来源:发表于2015-04-23 01:01 被阅读4621次

    题目:


    输入一个整形数组,数组里有正数也有负数。
    数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

    例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
    因此输出为该子数组的和18。

    分析:

    分析:O(n)的复杂度,也就是要求过一遍这个数组就要执行结束,要求最大的子数组,那么此子数组的开始大于0的值,向后读取,如果计算得到负值,那么前面的结果就不值得保留,从新从最新的地方加起。如果最后一个数是负值,那么最后一个值不需要,所以需要另一个参数来保留当前最大值。
    当然,如果这个数组全部是小于等于0,那么最大的值是绝对值最小的一个数,我们可以用一个数来保存

    solution

    <pre><code>

    include "stdio.h"

    include "stdlib.h"

    include "math.h"

    //找到字数组的最大和
    int find(int a ,int len){
    int sum=0;
    int b=0;//保留临时结果
    int i=0;
    //保留最小的绝对值,全负数组用
    int c=abs(
    a);

    for(;i<len;i++){
        if (abs(*(a+i))<c)
            c=abs(*(a+i));
        
        if(b<0){
            b=*(a+i);
        }else{
            b+=*(a+i);
        }
        if (*(a+i)>0){
            sum=b;
        }
    }
    if (sum!=0)
        return sum;
    else
        return -c;
    

    }

    int main(){
    int a[10]={1, -2, 3, 10, -4, 7, 2, -5};
    int b[10]={-10,-2,-3,-5,-9,-10,-18,-7};
    int c[10]={-10,-2,0,-5,-9,-10,-18,-7};
    printf ("a的子数组最大和是%d\n",find(a,8));
    printf ("b的子数组最大和是%d\n",find(b,8));
    printf ("c的子数组最大和是%d\n",find(c,8));
    return 0;
    }
    </code></pre>

    执行结果:

    <pre><code>
    a的子数组最大和是18
    b的子数组最大和是-2
    c的子数组最大和是0
    </code></pre>

    相关文章

      网友评论

      • 9cdbab6da4e9:评论区还有。。。
      • 一只冷布丁:刚在LeetCode上纠结这一题,然后就在如厕的时候看到了,真乃猿粪!
      • larryzhao:@Stansosleepy 诶,对噢,你这个留着,我们明天看一下,蛮奇怪的。
      • Stansosleepy:@larryzhao 不止啊,我的函数体好多内容都没了
      • larryzhao:@Stansosleepy 这个我们明天会看一下,是少了一个小于号是么?
      • Stansosleepy:简书处理markdown代码的时候好像还是有点问题啊!!!for循环代码如下:
        for(;i<0){
        b=*(a+i);
        }else{
        b+=*(a+i);
        }
        if (*(a+i)>0){
        sum=b;
        }
        }

      本文标题:求子数组的最大和(微软面试100题003)

      本文链接:https://www.haomeiwen.com/subject/npaufttx.html