题解 | #跳跃游戏(二)# 使用最大递增子序列的思想

当然这道题不要求递增，但是思想是类似的，需要加判断条件，另外，需要用变量m来优化时间复杂度

#include <iostream>
using namespace std;

const int N = 1e6;
int a[N], n, dp[N], m=0; // m 是数组元素的最大值

int main(){
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i];
		if( a[i] > m )
			m = a[i];
	}
		
	// 特例
	if( n == 0 ){
      cout << -1 << endl;
      return 0;
    }
		
  
	// dp数组初始化
	for(int i=1; i<n; i++)
		dp[i] = -1;
	dp[0] = a[0];
  
	for(int i=1; i<n; i++){
		int j = i - m >= 0 ? i-m : 0 ;
		for(; j<i; j++){
			if( a[j]+j >= i && dp[j] != -1 ){
				dp[i] = max( dp[i], dp[j]+a[i] );
			}
		}
	}
	
	cout << dp[n-1] << endl; 
	
	return 0;
}