最大和子数组 && 最大有序子数组

在O(n)的时间内，求取最大和的子数组以及最大升序子数组：

（一）给定一个数组，然后求取最大和的子数组：

（1）方法一：时间复杂度为O(n^2):

/*
 输入一个数组array,长度为n；
 得到最大子数组的范围left~right；
 返回最大子数组的和；
 */
 int maxSubsequenceSum(const int array[], int n,int &left, int & right){
  
  int tempSum=0;
  int maxSum=0;
  int templeft;
  int tempright; int i,j,k;
 for(i=0;i<n;i++){
  tempSum=0;
   templeft=i;  for(j=i;j<n;j++){//寻找从i到n-1的最大子数组
   tempSum+=array[j];
    tempright=j;   if(maxSum<tempSum){
     maxSum=tempSum;
     left=templeft;
     right=tempright;
    }  }
 }
 return maxSum;
}

----------
（2）方法二：

分析：设sum[i] 为前i 个元素中，包含第i 个元素且和最大的连续子数组，maxSum为子数组中最大和。则对于第i+1个元素来说：
如果sum[i]>0,则sum[i+1]=sum[i]+a[i+1];
如果sum[i]<0;则sum[i+1]=a[i+1];
然后maxSum=max{maxSum,sum[i+1]};
综上：sum[i+1]=max{a[i+1], sum[i]+a[i+1]};
maxSum=max{maxSum, sum[i+1]};

2)代码实现：

int maxSum(int * a, int n, int & start, int & end ){
  int maxSum=0;
  int tempSum=0;
  int tempStart=0;
  int tempEnd=0; for(int i=0;i<n;i++){
  if(tempSum<0){
   tempSum=a[i];
   tempStart=i;
   }
     else {
   tempSum+=a[i];
   tempEnd=i;
   }
     if(maxSum<tempSum){
    maxSum=tempSum;
    start=tempStart;
    end=tempEnd;
   } }
 return maxSum;
 }

缺陷：如果全是负数，则返回的会是0，可以初始化中
tempSum,maxSum均为a[0];

注意：容易出错的地方，之前写的是
if (tempSum<0) tempSum=a[i+1];
else tempSum+=a[i+1];
但是for循环中的i的范围为0~n-1,i+1就会越界。

3)改进：

int maxSum(int * a ,int n){
  int maxSum=a[0];
  int tempSum=a[0]; for(int j=0;j<n;j++){
   if(tempSum<0)
   tempSum=a[i];  else 
   tempSum+=a[i];  if(maxSum<tempSum){
    maxSum=tempSum;
   }
  } return maxSum;
 }

------------------------------------------------------------
（二）最大升序子数组：O(N)

(1)解析：动态规划思想；

 设maxLen[i]为当前最长的升序子序列的长度，

if(a[i-1]<a[i])
  tmpLen[i]++;
  else tmpLen[i]=1;
  maxLen[i]=max{maxLen[i-1],tmpLen[i]};

 (2)代码实现：

/*
 输入：数组：
 输出：最大和的子数组的起始地址，结束地址，以及最大和；
 注意：start，end为引用型参数；
  */ int longestSortedSubarray(int* array,int length,int *start,int* end){
        int tmpLen,longestLen;
        int tmpStart,tmpEnd;
        /*初始化*/
        *start=0;
        *end=0;
        tmpStart=0;
        tmpEnd=0;
        tmpLen=1;
        longestLen=1;        for(int i=1;i<length;i++){
        if(array[i]>array[i-1])
        {
            tmpLen++;
            tmpEnd=i;
        }
        else {
        tmpLen=1;
        tmpStart=i;
        tmpEnd=i;
        }        if(tmpLen>longestLen){
        longestLen=tmpLen;
        *start=tmpStart;
        *end=tmpEnd;
        }        }
  return longestLen;
  }