首页 > 大疆嵌入式编程题(2020.8.16)
头像
必胜offer必胜
编辑于 2020-08-17 15:48
+ 关注

大疆嵌入式编程题(2020.8.16)

编程题两道,都是关于动态规划的。

第一道,最大连续数组和。

要的是两段连续,且两段不能有重叠,求两个子段的最大和

(PS: 前面做题花了太多时间,最后慌慌张张的写了下第一题发现还剩10s, 点了下提交,发现报错了,哭了~)
例子:
输入:第一行测试用例数t,空一行后; 下一行第一个测试用例个数n;再下一行一个数组,空格隔开;再来行空;下一个用例

输入
3

10
1 -1 2 2 3 -3 4 -4 5 -5

5
-5 9 -5 11 20

10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

输出
13
40
-2
#include<bits/stdc++.h>
using namespace std;

int maxSum(vector<int>& data, int l, int r)
{
    int sum = 0, b = 0;
    for(int i = l; i<r+1; ++i)// 这里写成了 i=r
    {
        if(b>0) b += data[i];
        else b = data[i];
        sum = max(sum, b);
    }
    return sum;
}

int main()
{
    int t;
    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;

        vector<int> data(n);
        for (int i = 0; i < n; ++i)
        {
            /* code */
            cin>>data[i];
        }
        int ans = 0;
        for (int i = 0; i < data.size(); ++i)
        {
            /* code */
            int left = maxSum(data, 0, i);
            int right = maxSum(data, i+1, data.size()-1); //这里写成data.size()了,给整越界了/
            ans = max(ans, left+right);

        }
        cout<<ans;
    }
    return 0;
}
	
// 更新了代码 2020.8.17

第二题:

秒了一眼,好像是背包问题,感觉短时间做不出来。



全部评论

(5) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐