算法——求数组中最大子数组和

题目

有一输入数组，数组里面的数字都是整数，可能为正，可能为负，也可能是0，要求该输入数组中最大子数组的和。

题目分析
面对这样的一个问题，首先需要仔细分析问题的条件与问题所求。这个问题提供了一个输入数组，里面会有若干个元素，每个元素可以为正数，可以为负数，也可以为0。而题目要求输出该数组中最大子数组的和，注意是要求连续相邻的若干元素组成的子数组，并且保证该子数组的和最大。

这个问题具体最优子结构，无后效性等动态规划的特点，因此可以用动态规划来解决。

设原输入数组为data[]，利用另一个数组dp[i]来表示以data[i]结尾的子数组的最大和：

dp[i]=max(sum(data[start....end])) 0<=start<=end<=i

因此最大的子数组就是dp数组中的最大值。

在实际的代码实现中可以简化dp数组，用一个变量替代他，并且实时的更新最大和，以及子数组的起始位置和结束位置。

代码部分
下面是实现该题目的部分代码：

[cpp]
#define LENGTH 10

int max_subset(int *data,int len,int *s,int *l)
{
    int max=0;
    int i,j;
    int sum=0;
    int start,end;

    for(i=0;i<len;i++)
    {
        if(sum<=0)
        {
            sum=data[i];
            start=end=i;
        }
        else
        {
            sum=sum+data[i];
            end=i;
        }
        if(sum>max)
        {
            max=sum;
            *s=start;
            *l=end;
        }

    }

    if(max==0)
    {
        max=data[0];
        *s=*l=0;
        for(i=1;i<len;i++)
        {
            if(data[i]>max)
            {
                max=data[i];
                *s=*l=i;
            }
        }
    }
    return max;
}
int main()
{

    int data[LENGTH]={-1,-2,3,10,-4,7,-2,5,-9,-1};
    int result=0;
    int s,l;
    result=max_subset(data,LENGTH,&s,&l);
    printf(" max sub set is %d from %d to %d \n",result,s,l);

    return 0;
}

小结
这是一道经典的题目，被很多公司笔试面试所采用，值得仔细研究。

补充：软件开发 , C++ ,