[算法] 牛课题霸 - DP6 连续子数组最大和 - 动态规划

本文主要是介绍[算法] 牛课题霸 - DP6 连续子数组最大和 - 动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

DP6 连续子数组最大和

解题过程

思路一

两个for循环，遍历。
因为每个元素都要遍历两遍，所以时间复杂度O(n^2)。
简单的测试用例可以通过，但是提交时，一个巨大的数组用例，直接导致超时。

#include <iostream>
using namespace std;int GetSubMax(int n, int* data)
{int sum = 0;int res = 0;bool isinit = true;for(int i = 0; i < n; i++){sum = data[i];// cout << sum << endl;if(isinit) {res = sum;isinit = false;}elseres = res < sum? sum : res;for(int j = i +1; j < n; j++){sum += data[j];// cout << sum << endl;res = res < sum? sum : res;}}return res;
}int main() {int n;cin >> n;int* data = new int[n];for(int i = 0; i < n; i++){cin >> data[i];}cout << GetSubMax(n, data);
}
// 64 位输出请用 printf("%lld")

思路二

动态规划。看的答案才会的。官方思路：

TMD， 这算法怎么想出来的。我怎么没想到。

#include <iostream>
using namespace std;int GetSubMax(int n, int* data)
{int  max= 0, sum = 0;for(int i = 0; i < n; i++){if(i == 0){sum = data[i];max = sum;}else {sum = sum + data[i] > data[i] ? sum + data[i]: data[i];max = max > sum ? max : sum;}}return max;
}int main() {int n;cin >> n;int* data = new int[n];for(int i = 0; i < n; i++){cin >> data[i];}cout << GetSubMax(n, data);
}
// 64 位输出请用 printf("%lld")

这篇关于[算法] 牛课题霸 - DP6 连续子数组最大和 - 动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---