给定长度为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);
}
