#include 
     
      #include 
      
       using namespace std;/*求数组的子数组和的最大值分析：子数组是连续的，只用返回子数组的和，元素肯定是整数，包括正数，负数，0假设 sum存储的是数组从0第i个位置的最大子数组之和，那么第i+1个元素加入后的结果 temp = max(temp+a[i+1],a[i+1]); sum = max(sum,temp);(sum中始终存着最大和)*/int max(int a,int b){    return a>b?a:b;}int maxSum(int *arr,int n){    int temp = arr[0];    int sum = arr[0];    for (int i = 1; i < n; i++)    {        temp = max(temp+arr[i],arr[i]);        sum = max(sum,temp);    }    return sum;}//最长递增、递减子序列，这里以递增子序列为例，递减子序列可以转化为递增子序列计算/*设以 len[]数组存储 以每一个元素结尾的递增子序列的最大长度，没增加一个元素，更新len[0---i]len[i] = max{1,len[k]+1} a[i]>a[k] k:[0 i-1];该方法的效率为O(N^2)*/int LIS(int *arr,int n){    int *len = (int*)malloc(sizeof(int)*n);    if (len==NULL)return -1;    memset(len,0,n);    for(int i = 0; i < n; i++)    {        len[i] = 1;        for (int k = 0; k < i; k++)        {            if (arr[i] > arr[k] && len[k]+1 > len[i])                len[i] = len[k]+1;        }    }        int max=len[0];    for (int i = 0; i < n; i++)    if(len[i]>max)max = len[i];    free(len);    return max;}int main(int argc, char **argv){
        int a[] = {
   1,-1,2,-3,4,-5,6,-7};    int size;    int i;    size = sizeof(a)/sizeof(int);    int res = maxSum(a,size);    printf("最大子数组之和为：%d\n",res);    printf("最长递增子序列：%d\n",LIS(a,size));    return 0;}