最大子数组求解

总结一下目前的几种算法：

1：暴力求解：直接组合求解   

    for (int i = 0; i < array_length; i++)
    {
        for (int j = i ; j < array_length; j++)
        {
          
            //计算遍历的子数组之和
                subarraysum += A[j];
            //找出最大的子数组
            if (subarraysum>sum)
            {
                sum = subarraysum;
                low = i;
                height = j;
            }
        }
    }

2:分治策略

主要思想：考虑一个子数组a[i...j]的最大子数组可能出现三种情况 a. 出现在a[i..N/2],b.出现在a[N.2...j] ,c.包括a[N/2];

3:算法导论课后思想

主要思想1：利用a[1..i]的最大子数组计算a[1...i+1],可知两种情况 a,与a[1..i]相同，b，包含a[i+1],从后往前循环寻找

主要思想2：a[1:i]有两个数组，其中一个是最大子数组，另外一个是包含a[i]的最大子数组，重写思想1描述的两种情况，对于第二种情况可值分为两种情况 a，只有a[i+1b.为a[1：i]

的极右最大子数组加上a[i+1];

实现如下：

最大子数组求解

原文：https://www.cnblogs.com/lysnuaa/p/10459074.html