本文共 903 字，大约阅读时间需要 3 分钟。
??????????????????????????????????????????????????Kadane???????????????????O(N)????????N?
Kadane??????????????????????current_max??????max_sum????????????????????????????????????current_max??????????????O(N)????????????
#includeusing namespace std;int main() { int N; while (cin >> N) { int* a = new int[N]; for (int i = 0; i < N; ++i) { cin >> a[i]; } int max_sum = a[0]; int current_max = a[0]; for (int i = 1; i < N; ++i) { current_max = max(a[i], current_max + a[i]); max_sum = max(max_sum, current_max); } cout << max_sum << endl; delete[] a; } return 0;}
?????????????????????O(N)???????????N??1,000,000????
转载地址：http://vjojz.baihongyu.com/