ダイナミック・プランニング・トピック1-最大連続サブシーケンスと

7377 ワード

一、問題:a[]={0,−2,11,−4,13,−5,−2}で、最大連続サブシーケンスとを求める.二、問題分析:テーマには貪欲な思想が含まれている.エレメントを選択するときに、最初のエレメントと最後のエレメントが正数でなければなりません.これにより、サブシーケンスとが最大になります.しかし、ひたすらの貪欲は正しい結果を得ることができず、貪欲はすべての正数の和を求めるだけで、テーマは最適解を求め、サブ問題は独立しており、自然と動的計画を考えている.では、このような考えはどのように表現されているのでしょうか.まず、前と現在選択されている要素が現在選択されていない要素が大きい場合は、前の結果は避けましょう.表現は、dp[j−1]+a[j]

if(dp[j-1] + a[j] < a[j])
dp[j] = a[j];
else
dp[j] = dp[j-1] + a[j];

少し整理して,動的計画の状態遷移方程式を得た.

dp[j] = max(dp[j-1] + a[j] , a[j]);

四、サブ問題:前のj要素の最大サブシーケンスと.小問題の最適解により大問題の最適解を決定する.五、コード展示:

#include
#define max(x,y) (x) > (y) ? (x) : (y)
int a[] = {
     0, -2, 11, -4, 13, -5, -2};
int dp[101];
void solve()
{
     
	int n = sizeof(a) / sizeof(a[0]);//    a  
	int res = a[0];//  
	for(int j = 1; j <= n; j++)
	{
     
		dp[j] = max(dp[j-1] + a[j], a[j]);
		res = max(dp[j], res);
	}
	printf("%d
",res);
}
int main()
{
     
	solve();
	return 0;
}

LeetCode123.株を売買する最良のタイミングIII

cssはn番目から、その後のすべての要素を取得します.