HDU 1003 Max Sum——dp求最大连续和O(n)

HDU 1003 Max Sum——dp求最大连续和O(n)

sum[i] = max{sum[i - 1] + a[i], a[i]};

ans = max{ans, sum};

注意left和right值应该在更新ans时更新

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;int main(){ int T, n, a, flag = 0; scanf("%d", &T); while (T--) { scanf("%d", &n); int left = 1, right = 1, pos = 1, sum = 0, ans = -INF; for (int i = 1; i <= n; i++) { scanf("%d", &a); sum += a; if (sum > ans) { ans = sum; left = pos; right = i; } if (sum < 0) { sum = 0; pos = i + 1; } } if (flag++) printf("\n"); printf("Case %d:\n%d %d %d\n", flag, ans, left, right); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。