和最大字串（C语言）

和最大字串（C语言） 和最大字串（C语言）

参考博客：https://www.cnblogs.com/activeshj/p/4090817.html

问题描述

给你一个整型数组，其中的元素有正有负也有0，要求你找到一个连续的子串，子串的所有元素之和是所有的连续子串中最大的。

例子：给定一组数，n个，有正，有负。要求找到和最大的连续子串，比如：

5 ， 4， -10， 11， 2， 8， -5， 4， 2，-3，1

可以判断出和最大的连续子串是： 11， 2， 8， -5， 4， 2 其和为22 。

算法思路

• 如果暴力解法，可以把所有的字串都找出(两成循环找起始)，然后比较大小（再一层循环加法算和，与之前的最大和比较），这样算法复杂度是O(n^3)

我们可以换一种思路，使得算法复杂度变为O(n)：

假设已经找出了从0到i-1中的最大子串Maxpre，现在要处理加入元素i后的情况。

有两种可能：最大子串还是0到i-1中的那个最大子串，记为Maxpre；最大子串要包含元素i，记为Maxcur 。

比较Maxpre与Maxcur ，将大的赋值给Maxpre ，继续往后扫描，直到处理完最后一个元素，由此形成一个O(n)的算法。

思路详情

我们首先设定Maxcur和Maxpre的值都为0，它们的起始下标也都为0。

然后通过一层for循环首先去给Maxcur赋值（最大子串要包含元素i，记为Maxcur）。

• 如果Maxcur加上a[i]的和＞=0，说明Maxcur子串的end索引可以继续往后走（因为 (后面紧接的数 +
  前面一个和≥0的子串)只会 ≥
  后面的数），但这并不说明Maxcur的begin和end的索引就是当前0-i的和最大字串（因为同时还要和0到i-1中的那个最大子串Maxpre比较，而这个子串有可能不包含a[i]）
• 如果Maxcur加上a[i]的和＜0。说明包含这个a[i]会使得后面的数 + 前面Maxcur记录的和子串一定会 <
  自身，所以我们要找最大子串，前面的就可以舍弃必须要在此时的i处Maxcur要清零，并且索引从i+1开始继续寻找子串。注意：清零以后Maxcur一定会
  < Maxpre，说明清零以后的这个Maxpre仍保留的是前面0-i和最大的子串（而且子串不包括a[i]）。

//MaxCur清零
MaxCur = 0;
MaxCurIdx.begin = i + 1;
MaxCurIdx.end = i + 1;

思路图形化

代码实现

#include 
#include 
#define MAXSIZE 11

typedef struct subIdx {
    int begin;
    int end;
} SUB_IDX;

typedef struct maxSub {
    SUB_IDX subPosition;
    int sum;
} MAX_SUB;

MAX_SUB * MaxSubScan(const int* array, int len)
{
    SUB_IDX MaxPreIdx;
            MaxPreIdx.begin = 0;
            MaxPreIdx.end = 0;
    SUB_IDX MaxCurIdx;
            MaxCurIdx.begin = 0;
            MaxCurIdx.end = 0;
    int MaxPre = 0;
    int MaxCur = 0;
    int i;

    for (i = 0 ; i < len; i++) {
        if ((MaxCur + array[i]) > 0) {
            MaxCur = MaxCur + array[i];
            MaxCurIdx.end = i;
        } else {
            MaxCur = 0;
            MaxCurIdx.begin = i + 1;
            MaxCurIdx.end = i + 1;
        }

        if (MaxCur > MaxPre) {
            MaxPre = MaxCur;
            MaxPreIdx.begin = MaxCurIdx.begin;
            MaxPreIdx.end = MaxCurIdx.end;
        }
    }

    MAX_SUB *maxsub = (MAX_SUB *) malloc( sizeof(MAX_SUB) );
    maxsub->subPosition.begin = MaxPreIdx.begin;
    maxsub->subPosition.end = MaxPreIdx.end;
    maxsub->sum = MaxPre;

    return maxsub;
}

int main()
{
    int a[MAXSIZE] = {5 ,4 ,-10 ,11 ,2 ,8 ,-5 ,4 ,2 ,-3 ,1};
    MAX_SUB *maxsub_result = (MAX_SUB *) malloc( sizeof(MAX_SUB) );
    maxsub_result = MaxSubScan(a,MAXSIZE);
    int beginindex,endindex,i;

    beginindex = maxsub_result->subPosition.begin;
    endindex = maxsub_result->subPosition.end;
    printf("beginindex:%d->%dn",beginindex,a[beginindex]);
    printf("endindex:%d->%dn",endindex,a[endindex]);
    printf("子串为：");
    for(i=beginindex;isum);

}

截图