洛谷 P1115 最大子段和 C语言 记忆化搜索

题目：

https://www.luogu.com.cn/problem/P1115?contestId=215526

寻找以i为结尾的子序列最大值，从1~n，并用记忆数组mem【i】储存。意距离，mem【3】是第三个元素为结尾的，子序列最大值，所以求第四个元素为结尾子序列最大值的时候，只需要比较第四个元素和第四个元素+mem【3】即可。

#include<iostream>
using namespace std;	
int n;
int nums[200000];
int mem[200000];
int dfs(int x)
{int sum = 0;if(x < 0)return 0; if(mem[x])return mem[x];sum = max(nums[x],dfs(x-1)+nums[x]);mem[x] = sum;return sum;
}
int main(void)
{cin >> n;int ans = -100;for(int i = 0 ; i < n ;i++)cin >> nums[i];for(int i = 0 ; i < n ; i++){ans = max(ans,dfs(i));}cout << ans;return 0;
}