求数组中顺序子集和最大的值（详细图解）

57 阅读 0 评论 38 点赞

我是靠谱客的博主斯文铃铛，最近开发中收集的这篇文章主要介绍求数组中顺序子集和最大的值（详细图解），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1、题目：

给定一组数，求其中任何一组顺序子集和最大的值。
　例如下面一组数据：
　　1 ， 2 ， -4 ， 7 ， 8 ， -2 ， 4；
　和最大的一组子集应该是：
　　7 ， 8 ， -2 ， 4 （总和：17）

2、分析：

　　这个题如果用蛮力法肯定是可以解决的，但是复杂度过高，不适宜大型数据组合的情况。我们看上面的例子，一开始设置两个指针指向起点1，分别表示累加的最大值maxValue，当前指向指针startPoint，从前往后遍历求和。如果第i个元素前面元素的和<=0，那么当前值加上前面的元素算和肯定比重新开始算和的值小，这时候就需要重新起头你的指针，从头计算累加值。如果前面的和比0大，不管其中是否有负数，加上前面的元素哪怕只有1，都比现在nArr[i]单个元素大。
　　如下图解释，当指针累加到-4的时候，前面和-1，小于等于0，如果和后面的数7累加到一起会削弱，所以前面的3个数都要舍弃，然后startPoint指针重新从7开始累加。每加一个数就和当前最大值maxValue比较，如果比它大就更新最大值maxValue。
这里写图片描述

3、程序：

#include<iostream>
using namespace std;

int maxSubset(int nArr[], int len)
{
    //开始起点都是数组第一个元素
    int maxValue = nArr[0];
    int startPoint = nArr[0];
    for(int i=1;i<len;i++)
    {
        //如果第i个元素前面元素的和<=0，那么加上前面的元素算和肯定比重新开始算和的值小
        if(startPoint<=0)
            startPoint = nArr[i];
        //如果前面的和比0大，不管其中是否有负数，加上前面的元素哪怕只有1，都比现在nArr[i]单个元素大
        else
            startPoint += nArr[i];
        //如果有大的子集了就刷新maxValue
        if( maxValue < startPoint)
            maxValue = startPoint;
    }

    return maxValue;
}

int main( )
{
    int nArr[] = {1,2,2,-2,3,4,7,-5,-10,3};
    int maxValue;
    maxValue = maxSubset(nArr,sizeof(nArr)/sizeof(int));
    cout<<maxValue<<endl;

    return 0;
}