C++程序设计：最大的子序列价值之和

桃扇骨 2022-12-21 10:56 127阅读 0赞

# 题目描述 #

给定一个长度为n的整数数列a1,a2,…,an，将这个数列分成若干段连续子序列，并且使得这些连续子序列的价值之和最大。

我们定义一个连续子序列的价值为：这个子序列中最大值与最小值的差。

# 输入格式 #

第一行包括一个整数n，代表数列长度。  
第二行n个整数，其中第i个整数代表数列的第i个元素ai，相邻的数字之间以一个空格分隔。

# 输出格式 #

一个整数，表示所有的划分方案中，子序列价值之和的最大值。

# 输入输出样例 #

## 输入1 ##

5  
1 2 3 1 2

## 输出1 ##

## 输入2 ##

3  
3 3 3

## 输出2 ##

# 数据规模说明 #

1<=n<=106,10\-9<=ai<=109

# 题解 #

这是一道典型的动态规划题目。

对于下标从i到j的子序列，只有两种情况：  
分割、不分割。

对于分割，不管分割成几段，都可以先按两段处理，剩下的便是两个子问题需要解决的事情；对于不分割，直接取这一段的最值求差值即可。

因此定义dp\[i\]\[j\]代表从i到j的子序列的最大价值。

# 代码 #

#include<iostream>
    #include <cmath>
    using namespace std;
    int main() { 
    	int n;
    	cin>>n;
    	int a[n];
    	for(int i=0; i<n; i++) { 
    		cin>>a[i];
    	} 
    	int mmax[n][n],mmin[n][n],dp[n][n];
    	for(int i=0; i<n; i++) { 
    		mmax[i][i]=a[i];
    		mmin[i][i]=a[i];
    		dp[i][i]=0;
    	}
    	//动态规划
    	for(int len=1; len<n; len++) { 
    		for(int i=0; i+len<n; i++) { 
    			//拆成两个 或者 只看一个 
    			int temp=0;
    			for(int t=i; t+1<=i+len; t++) { 
    				if(dp[i][t]+dp[t+1][i+len]>temp) { 
    					temp=dp[i][t]+dp[t+1][i+len];
    				}	
    			}
    			mmax[i][i+len]=max(mmax[i][i],mmax[i+1][i+len]);
    			mmin[i][i+len]=min(mmin[i][i],mmin[i+1][i+len]);
    			if(mmax[i][i+len]-mmin[i][i+len]>temp)
    				temp=mmax[i][i+len]-mmin[i][i+len];
    			dp[i][i+len]=temp;
    		}
    	}
    	cout<<dp[0][n-1];
    	return 0;
    }