最大の連続サブシーケンスの和(出力サブシーケンス版)
1742 ワード
動的計画を学習する時、この連続サブシーケンスを求める最大と問題を見て、いくつかのブログを見た後、普通はテーマの要求に従っていることを発見して、ただ最大の和を出力して、そこで私はどのようにサブシーケンスも負けたいと思っています.
まず単純に最大和を出力するときについてお話ししましょう.コア部分コードを参照:
これは私が他のブロガーから取ってきたもの(コピーではないので少し違いますが、意味の差は多くありません)、このコードはすべて負の数であることを考慮しないので、意味があまりありません.cur_sumが0未満の場合、cur_sum=0というのは、前の段のデータを1つの全体と見なし、この全体の和を負数とし、1つの負数を加えると必ずデータが減少することに相当するので、前の全体を捨ててcur_sum = 0.
出力サブシーケンスおよび:
変数lockを定義し、このフラグでシーケンスの開始位置を更新すべきかどうかを判断することを考えます.
新しいMAX値が同時にcur_を通過するとsum<0の場合,lはシーケンスの開始位置を更新するとともにlock変数を反転させる.
final:フルコード
まず単純に最大和を出力するときについてお話ししましょう.コア部分コードを参照:
cur_sum += num;
if(max < cur_sum ){
max = cur_sum;
}
if (cur_sum < 0){
cur_sum = 0;
}
これは私が他のブロガーから取ってきたもの(コピーではないので少し違いますが、意味の差は多くありません)、このコードはすべて負の数であることを考慮しないので、意味があまりありません.cur_sumが0未満の場合、cur_sum=0というのは、前の段のデータを1つの全体と見なし、この全体の和を負数とし、1つの負数を加えると必ずデータが減少することに相当するので、前の全体を捨ててcur_sum = 0.
出力サブシーケンスおよび:
変数lockを定義し、このフラグでシーケンスの開始位置を更新すべきかどうかを判断することを考えます.
新しいMAX値が同時にcur_を通過するとsum<0の場合,lはシーケンスの開始位置を更新するとともにlock変数を反転させる.
lock = 0;
if(max < cur_sum ){
max = cur_sum;
if(lock){
temp_l = i;
temp_e = i;
lock = 0;
}
temp_e = i;
}
if (cur_sum < 0)
{
cur_sum = 0;
lock = 1;
}
final:フルコード
#include
#include
#include
#include
int main(int argc, char const *argv[])
{
srand((unsigned)time(0));
int total,max = 0,cur_sum = 0,lock = 0,num ;
int temp_l = 0,temp_e = 0;
total = rand()%60+150;
for(int i = 0;i < total;i++){
if(i%6 == 0) printf("
");
num = rand()%31 - 15;
cur_sum += num;
printf("[%4d]%3d|%5d\t\t",i, num,cur_sum);
//
if(max < cur_sum ){
max = cur_sum;
if(lock){
temp_l = i;
temp_e = i;
lock = 0; // , lock
}
temp_e = i;
}
if (cur_sum < 0)
{
cur_sum = 0;
lock = 1; //lock
}
}
printf("
%d %d|max = %d
",temp_l,temp_e,max );
return 0;
}