给定长度为n的正整数序列a1,a2,…,an。 求一个递增的子序列，和最大。

输入：
第一行，n，表示给定序列的个数。 第二行，n个用空格隔开的正整数。

输出：
递增子序列的最大和。
数据范围限制

n ≤ 1000, 0 ≤ ai ≤ 100000。

思路：

动态规划的关键点是需要正确的找到的子问题 以及正确的划分好状态值
在该问题当中 用max_sun[]数组存放 对应索引处的最大值 需要先将其每个值设置为输入数组的值 这是因为 1 3 2 4 4 在这个数组当中 索引为2的点 最大子序列的和 为 2 所以先将每一个值设置为输入数组的值

#include<stdio.h>

// 递增子序列最大和

#define M 5
int max_sum[5]= {-1};

int sloveMax(int arr[]);
int main() {

    int nums[M]= {1, 10, 3, 2, 5}; // 11 最大和是11 递增子序列1 2 3 5
    int max_sum_num = sloveMax(nums);
    printf("max num:%d\n",max_sum_num);
    for(int i = 0; i<M; i++)
        printf("max_sum[%d]:%d\n",i,max_sum[i]);
    return 0;
}

// 到底该怎么找到动态规划的值

// 数组的名字是指针常量 不能放在等号的左边用于赋值

int arrMax(int arr[]) {
    int maxNum=0;
    for(int i = 0; i < M; i++) {
        if(arr[i]>maxNum)
            maxNum=arr[i];
    }
    return maxNum;
}

int sloveMax(int arr[]) {
    int i = 0;
    int j = 0;
    max_sum[i]=arr[i];
    int flag = 1;
    for(i = 1; i < M; i++) {
        flag=1;
        for(j = 0; j < i; j++) {
            if(arr[j] > arr[i]) {
//              printf("arr[%d]:%d\n",j,arr[j]);
                flag=0;
                break;
            }
        }
        if(flag==0)
            max_sum[i] = max_sum[j-1]+arr[i];
        else {
            max_sum[i] = arrMax(max_sum)+arr[i];
        }
    }
    return  arrMax(max_sum);
}