腾讯2012实习生招聘题求子数组的最大和

原有题目没有考虑到全是负数，输出最大负数，而是采取输出0； (function(w, d, g, J) { var e = J.stringify || J.encode; d[g] = d[g] || {}; d[g]['showValidImages'] = d[g]['showValidImages'] || function() { w.postMessage(e({'msg': {'g': g, 'm':'s'}}), location.href); } })(window, document, '__huaban', JSON);

好的参考资料 http://blog.csdn.net/v_july_v/article/details/6444021 

#include <stdio.h>
#include <stdlib.h>
/*遍历求子数组最大和 时间复杂度为o(n^2)*/
int maxsum(int *a,int n)
{
    int s1 = 0,s2 = 0;
    int i,j;

    for(i = 0;i < n; i++)
    {
        s1 = 0;
        for(j = i;j < n; j++)
        {
            s1 += a[j];
            if(s1 > s2)
                s2 = s1;
        }
    }
    return s2;
}
/* 求子数组最大和 时间复杂度为o(n)*/
int maxsum2(int *a,int n)
{
    int i;
    int s1 = 0,s2 = 0;

    for(i = 0;i < n;i++)
    {
        s1 += a[i];
        if(s1 < s2)
            s1 = (s1 > a[i]) ? s1 : a[i];
        else if(s1 >= s2)
            s2 = s1 = (s1 > a[i]) ? s1 : a[i];
    }
    return s2;
}
int maxsum3(int *a,int n)
{
    int i;
    int sum = 0,b = 0;

    for(i = 0;i < n;i++)
    {
        if(b < 0)
          b = a[i];
        else
          b += a[i];
        if(b > sum)
            sum = b;
    }
    return sum;
}
/*全为负数时输出最大负数*/
int maxsum4(int *a,int n)
{
    int i;
    int sum = a[0] ;
    int b = 0;

    for(i = 0;i < n;i++)
    {
        if(b < 0)
          b = a[i];
        else
          b += a[i];
        if(b > sum)
            sum = b;
    }
    return sum;
}
int main()
{
    int array[] = {-1,2,4,3,-6,8,-1,10,-3,8};

    int n = sizeof(array)/sizeof(array[0]);
    int sum1 = 0,sum2 = 0,sum3 = 0;
    sum1 = maxsum(array,n);
    printf("max sum1 of array :%d\n",sum1);

    sum2 = maxsum2(array,n);
    printf("max sum2 of array :%d\n",sum2);

    sum3 = maxsum3(array,n);
    printf("max sum3 of array :%d\n",sum3);
    int array1[] = {-1,-2,-3,-4};
    int n1 = sizeof(array1)/sizeof(array1[0]);
    int sum4;
    sum4 = maxsum4(array1,n1);
    printf("max sum4 of array :%d\n",sum4);

    printf("Hello world!\n");
    return 0;
}