问题描述:
有一句子列表,保存有长度、句子起始位置、包含关键字数量
现需要找出连续的若干句 在[min,max]长度范围内使其包含的关键字总数最多
变量定义
total_key_num:N句关键字总数
total_len:N句总长度
sents:句子列表{int len, int key_num}
from:N句起始位置
to:N句结束位置(包含)
解决方法:
抛弃重复遍历
先找出前N句,使total_len在[min,max]范围内,并保存total_key_num
下移from 并在total_len中减去sents[from].len total_key_num中减去sents[from].key_num
下移to 直到total_len in [min, max]
沿途保存信息 即可在一次遍历后生成需要的信息 问题得解