首页 > 代码库 > 求最大子串
求最大子串
int n, a[maxn]; int maxSubstr() { int sum = 0, minsum = 0, answer = 0; for (int i = 1; i <= n; ++ i) { sum += a[i]; minsum = min(sum, minsum); answer = max(answer, sum - minsum); } return answer; }
进阶版
/*二、给你两列数 A; B, 定义一个子串 [l; r] 的权值为 ∑r i=l Ai k= ___________ ∑r i=l Bi 问权值最大的子串.*/ const double inf = 1e32; int n, a[maxn], b[maxn]; double c[maxn]; double maxSubstr() { double sum = 0, minsum = inf, answer = -inf; for (int i = 1; i <= n; ++ i) { sum += c[i]; answer = max(answer, sum - minsum); minsum = min(sum, minsum); } return answer; } double erfen() { double l(-inf), r(inf); while (l + 1e-10 < r) { double mid = (l + r)/ 2; for (int i = 1; i <= n; ++ i) { c[i] = a[i] - mid * b[i]; } if (maxSubstr() >= 0) { l = mid; } else { r = mid - 1e-10; } } //把分母乘过去二分答案
求最大子串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。