#include <iostream>
#include <string>
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;
}