在求连续区间的最大和是一种动态规划的常见例题。
那么如何能快速求算得一个长度为n的数组的最大连续区间和?
第一反应当然是,通过暴力计算每一个区间的和进而求其最大值。
但时间复杂度到达了不可接受的O(n^2)...
而比较好的算法如下:
#includeusing namespace std; #define ll long long #define endl 'n' //#include ll A[10003]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //求连续区间最小:时间:O(n) 空间:O(n) ll len, temp, ans = 0, dp = 0; cin >> len; for (int i = 0; i < len; ++i) { cin >> A[i]; //输入数组第i个值temp=Arr[i] dp = max(A[i], A[i] + dp); //以Arr[i]结尾的区间最大值 ans = max(ans, dp); } cout << ans << endl; }
显然,最大连续区间一定是以某个数为结尾的区间。
不妨假设以A[i]结尾的最大连续区间和为dp[i]。
那么,我们只需要遍历原数组,比较A[i]以及A[i]+dp[i-1].
(即,当dp[i-1]<0时,直接舍弃前面的区间,以A[i]做dp[i],反之连接上之前的区间即可)
再退一步想,如果不查找区间位置,好像并没有存储数组的必要...
此时直接用temp接受临时的A[i]即可。
#includeusing namespace std; #define ll long long #define endl 'n' //#include int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //求连续区间最小:时间O(n) 空间O(1) ll len, temp, ans = 0, dp = 0; cin >> len; for (int i = 0; i < len; ++i) { cin >> temp; //输入数组第i个值temp=Arr[i] dp = max(temp, temp + dp); //以Arr[i]结尾的区间最大值 ans = max(ans, dp); } cout << ans << endl; }
以上代码运用了动态规划的思想,通过求算Arr[i]结尾的区间最大值dp[i]的最大值为原数组Arr[i]的最大连续区间和。并且舍弃了原来的数组...所以它只能求和不能求区间的位置
#includeusing namespace std; #define ll long long #define endl 'n' //#include ll A[10003]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //求连续区间最小:时间:O(n) 空间:O(n) ll len, temp, ans = 0, dp = 0, left, right = 0; cin >> len; for (int i = 0; i < len; ++i) { cin >> A[i]; //输入数组第i个值temp=Arr[i] dp = max(A[i], A[i] + dp); //以Arr[i]结尾的区间最大值 if (dp > ans) { ans = dp; //更新答案以及右区间 right = i; } } cout << ans << endl; for (int i = right; i >= 0; --i)//寻找左区间位置 { ans -= A[i]; if (ans == 0) { left = i; break; } } cout << "最大连续区间为: [ " << left << " , " << right << " ]n"; }
以上通过存储数组来查找区间位置:
当然,除了动态规划的方法还有分治等方法,但总的来说dp便于理解。
文章制作不易,有不对的还望斧正。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)