php在网站后台建设中的优势,网站设计有哪些语言版本,手机网站建设软件有哪些内容,做吃的网站输入：整数序列a1,a2,…,an 输出：序列的一个子段，其和Σak最大 注意：当所有整数都为负数时，定义最大子段和为0 使用动态规划，输入数组是a[n]； 状态转移方程dp[i]=max(dp[i-1]+a[i],a[i])——这个状态方程可以发现，使得满足“连续”这一要求的重点在于每个dp[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
