当前位置:   article > 正文

大疆嵌入式软件笔试题2020.8.16_大疆笔试题动态规划

大疆笔试题动态规划

嵌入式软件岗,两道编程题都是动态规划。

第一题:求出数组中两个不重叠的子数组的最大和。

POJ 2479Maximum sum 

  1. #include <vector>
  2. #include <cstdio>
  3. using namespace std;
  4. int helper(const vector<int>& v)
  5. {
  6. int n = v.size();
  7. vector<int> left(n), right(n);
  8. //left[i]: 以i结尾的子数组最大和, right[j]: 以j开头的子数组最大和
  9. left[0] = v[0];
  10. for(int i = 1; i < n; i++) left[i] = max(left[i-1], 0) + v[i];
  11. right[n-1] = v[n-1];
  12. for(int j = n - 2; j >= 0; j--) right[j] = max(right[j+1], 0) + v[j];
  13. vector<int> lmax(n), rmax(n);
  14. //lmax[i]: [0...i]中子数组的最大和, rmax[j]: [j...n-1]中子数组最大和
  15. lmax[0] = left[0];
  16. for(int i = 1; i < n; i++) lmax[i] = max(lmax[i-1], left[i]);
  17. rmax[n-1] = right[n-1];
  18. for(int j = n - 2; j >= 0; j--) rmax[j] = max(rmax[j+1], right[j]);
  19. int ans = -1e9;
  20. for(int i = 0; i < n - 1; i++)
  21. {
  22. ans = max(ans, lmax[i] + rmax[i+1]);
  23. }
  24. return ans;
  25. }
  26. int main()
  27. {
  28. int q;
  29. scanf("%d", &q);
  30. for(int query = q; query > 0; query--)
  31. {
  32. int n;
  33. scanf("%d", &n);
  34. vector<int> v(n);
  35. for(int i = 0; i < n; i++) scanf("%d", &v[i]);
  36. printf("%d\n", helper(v));
  37. }
  38. return 0;
  39. }

两道可以采用相似思路去做的题目:

1477. 找两个和为目标值且不重叠的子数组

给你一个整数数组 arr 和一个整数值 target 。

请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案,请你返回满足要求的两个子数组

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/994084
推荐阅读
相关标签
  

闽ICP备14008679号