金匮肾气丸治疗高血压:求子数组的最大和111

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。        例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。         如果不考虑时间复杂度，我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是，由于长度为n的数组有O(n²)，具体是n*(n+1)/2个子数组；而且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思路的时间是O(n³)。 我们试着再观察这个数组的特点，一个元素一个元素的看。根据A[0]是否在这个满足最大和的子数组中，我们可以分为两种情况。1.       在。那么可以从A[0]开始求（比较容易）。2.       不在。那么这种情况，又可以继续分为两种情况：A[1]在不在这个满足最大和的子数组中。从这里我们可以观察出一种递归的特点，可以把一个规模为N的问题转化为规模为N-1的问题。所以这个从A[0]到A[n-1]的最大和子数组问题分解成：1.       所求子数组中包含A[0]。如果不包含A[1]，则A[0]自己满足条件，此时Max（A[0]……A[n-1]）=A[0]。如果包含A[1]，则Max（A[0]……A[n-1]）=A[0]+Max（A[1]……A[n-1]）。2.       所求子数组中不包含A[0]。Max（A[0]……A[n-1]）=Max（A[1]……A[n-1]）。最终结果取以上三者的最大值即可，即Max（A[0]……A[n-1]）=max（ A[0], A[0]+Max（A[1]……A[n-1]）, Max（A[1]……A[n-1]））。 这个的复杂度为线性：因为只要把数组遍历一遍即可。代码如下：
 1 int MaxSubSum(int *A,int n)
 2 {
 3     //假设满足最大和的子数组就是从StartFrom[i]开始
 4     int *StartFrom = new int[n];
 5     memset(StartFrom,n,0);
 6     StartFrom[n-1] = A[n-1];
 7     //假设A[i]之后满足最大和的子数组的和为Longest[i]（不一定包括A[i]）
 8     int *Longest = new int[n];
 9     memset(Longest,n,0);
10     Longest[n-1] = A[n-1];
11
12     for (int i = n-2 ; i >= 0 ; i--)
13     {
14         //如果从i开始，那么要么最大和只包括A[i]自己，要么就是后面的那个序列连上A[i]
15         StartFrom[i] = max(A[i],A[i]+StartFrom[i+1]);
16         //最大和，要么是从i开始的，要么还是以前的
17         Longest[i] = max(StartFrom[i],Longest[i+1]);
18     }
19     //最后结果是在号元素中保存
20     return Longest[0];
21 }
22

由于这种前后单元素的相关性，实际上不需要两个数组来储存这个信息，只需要两个变量即可，这样可以减小程序的空间复杂度。
代码如下：  1 int MaxSubSum(int *A,int n)
 2 {
 3     //假设满足最大和的子数组就是从StartFrom开始
 4     int StartFrom = A[n-1];
 5     //假设A[i]之后满足最大和的子数组的和为Longest（不一定包括A[i]）
 6     int Longest = A[n-1];
 7
 8     for (int i = n-2 ; i >= 0 ; i--)
 9     {
10         //如果从i开始，那么要么最大和只包括A[i]自己，要么就是后面的那个序列连上A[i]
11         StartFrom = max(A[i],A[i]+StartFrom);
12         //最大和，要么是从i开始的，要么还是以前的
13         Longest = max(StartFrom,Longest);
14     }
15     //最后结果是在0号元素中保存
16     return Longest;
17 }
 输出子序列的起点和终点，并输出该子序列的和#include
#include
#include
#include

int main(){
    int *ip;
    int j,length,max,sum;
    int start1 = 0 ,start2 = 0;
    
    printf("Please enter the array's length:");
    scanf("%d",&length);
    if((ip = (int*)malloc(length*sizeof(int)))==NULL)
    {
            fprintf(stderr,"Malloc memory failed !");
            exit(1);
    }
    printf("Enter eath element:");
    for(j = 0; j < length ; j ++)
    scanf("%d",ip+j);

    max = INT_MIN;
    for(sum = j = 0; j < length; j ++)
    {
            sum += *(ip+j);
            if(max < sum)
            {
                    start1 = start2;
                    max = sum;
            }
            if(sum < 0){
                    start2 = j+1;
                    sum = 0;
            }
     }
     for(j = start1,sum = 0; sum != max; j ++)
            sum += *(ip+j);
     printf("\nThe subsequence from %d to %d,max sum is %d\n",start1,j-1,max);
  return 0;
}