百姓网网站建设,wordpress 标签 文章,网站开发 0755,html5培训网站模板输入#xff1a;整数序列a1,a2,…,an 输出#xff1a;序列的一个子段#xff0c;其和Σak最大 注意#xff1a;当所有整数都为负数时#xff0c;定义最大子段和为0 使用动态规划#xff0c;输入数组是a[n]#xff1b; 状态转移方程dp[i]max(dp[i-1]a[i],a[i])——这个状… 输入整数序列a1,a2,…,an 输出序列的一个子段其和Σak最大 注意当所有整数都为负数时定义最大子段和为0 使用动态规划输入数组是a[n] 状态转移方程dp[i]max(dp[i-1]a[i],a[i])——这个状态方程可以发现使得满足“连续”这一要求的重点在于每个dp[i]都包含了当前元素a[i] 使用两个数组start,end分别记录dp[i]的起始数组元素下标start[i]和dp[i]的终止数组元素下标end[i]——方便最后可以最大子段的每个元素 使用max记录dp[i]的最大值maxi_i记录下标
//dp[i]max{dp[i-1]a[i],a[i]}
#includeiostream
#includevector
using namespace std;
#define MAX 100000
int main() {int dp[MAX];//dp[i]表示前i的数包含a[i]的最大子段和int a[MAX];vectorintstart,end;//start[i],end[i]记录dp[i]的起始下标和终止下标int n;//数组a的长度cin n;bool flag 0;//判断数组元素是不是全非正数for (int i 0; i n; i) {cin a[i];if (a[i] 0)//数组元素存在正数flag 1;}if (flag 0) {//如果数组a所有元素都是非正数则输出0cout 0 endl;return 0;}dp[0] a[0];//初始化dp[0],start[0],end[0]start.push_back(0);//end.push_back(0);//int max 0xffffffff;//记录dp[i]的最值int max_i;//记录使得dp[i]取得最值的下标ifor (int i 1; i n; i) {if (dp[i - 1] a[i] a[i]) {//状态转移方程dp[i] dp[i - 1] a[i];start.push_back(start[i - 1]);//随dp[i]更新start数组}else {dp[i] a[i];start.push_back(i);}end.push_back(i);//随着dp[i]更新end数组if (dp[i] max) {//寻找最大dp[i]max dp[i];max_i i;}}for (int i start[max_i]; i end[max_i]; i) {//输出最大子段cout a[i] ;}return 0;
}
