赞
踩
嵌入式软件岗,两道编程题都是动态规划。
第一题:求出数组中两个不重叠的子数组的最大和。
- #include <vector>
- #include <cstdio>
- using namespace std;
-
- int helper(const vector<int>& v)
- {
- int n = v.size();
- vector<int> left(n), right(n);
- //left[i]: 以i结尾的子数组最大和, right[j]: 以j开头的子数组最大和
- left[0] = v[0];
- for(int i = 1; i < n; i++) left[i] = max(left[i-1], 0) + v[i];
- right[n-1] = v[n-1];
- for(int j = n - 2; j >= 0; j--) right[j] = max(right[j+1], 0) + v[j];
-
- vector<int> lmax(n), rmax(n);
- //lmax[i]: [0...i]中子数组的最大和, rmax[j]: [j...n-1]中子数组最大和
- lmax[0] = left[0];
- for(int i = 1; i < n; i++) lmax[i] = max(lmax[i-1], left[i]);
- rmax[n-1] = right[n-1];
- for(int j = n - 2; j >= 0; j--) rmax[j] = max(rmax[j+1], right[j]);
-
- int ans = -1e9;
- for(int i = 0; i < n - 1; i++)
- {
- ans = max(ans, lmax[i] + rmax[i+1]);
- }
- return ans;
- }
-
- int main()
- {
- int q;
- scanf("%d", &q);
- for(int query = q; query > 0; query--)
- {
- int n;
- scanf("%d", &n);
- vector<int> v(n);
- for(int i = 0; i < n; i++) scanf("%d", &v[i]);
- printf("%d\n", helper(v));
- }
- return 0;
- }

两道可以采用相似思路去做的题目:
给你一个整数数组 arr 和一个整数值 target 。
请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案,请你返回满足要求的两个子数组
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。