找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6337|回复: 1
收起左侧

[基础刷题题目讨论] Codility上的challenge Aluminium 2014

[复制链接]
发表于 12-4-2014 11:02 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 cpcs 于 12-4-2014 05:46 PM 编辑

题目说了一大堆,简单来说就一句话,在一个数组中,允许交换两个元素的位置,只允许交换一次(可以自己和自己交换,相当于不交换),求最大子段和。


数组元素范围 [-10^4,+10^4]


函数头部:


int solution(vector<int> &A);


要求时间复杂度 O(N),空间复杂度O(N)。


分析:这是我比较喜欢的一个题,它在传统的最大子段和上做了一些改动。之前尝试过从最大子段和方法上做修改,例如换一个元素,删一个元素等等,都挂了。后来和管神讨论,发现可以dp,dp也是很巧妙的。

设f表示以i结尾的一段连续的最大子数组外加单独一个元素的最大和。这里需要多说几句,这个定义非常重要。首先:

(1) 以i结尾的连续一段可以为空,但如果非空的话,一定要以i结尾 (废话)

(2) 单独存在的一个点不能为空,并且这个点不能在(1)之内 (同一个元素不能加两次嘛)

定义这个的目的是,如果我们有了这个值,那个单独的元素就是我们换入最终结果的元素。


那么f的递推式是 f = max(f[i - 1] + A, max{A[0..i]}} 前者对应以i结尾的连续一段非空的情况,这个和传统最大子段和很像…… 后面那个其实是如果连续一段为空,按照f的定义,我们只能取一个点,那么这个点显然要取A[0..i]最大的。如此,我们定义好了f。

再定义一个g,这个g是和传统最大子段和定义是一样的,g表示以i开头的最大子段和。这个不多说g = max(g[i + 1] , 0) + A, 那么我们倒着循环i的时候(i = n - 2..0)顺便能求出每个g的值,并且也能求出不交换的普通的最大子段和。也就是max{g[0..n-1]}。

那么对于交换的情况,我们考虑A和某个元素j < i做了交换,那么其实结果是g - a + f[i - 1] , 也就是说f[i - 1]里面包含了a要换入的元素。所以我们再循环一次取max就行了。

可是这种交换值对应了i和j < i的交换。 所以我们还需要把A中的元素翻转,再计算一次。

代码:

  1. // you can use includes, for example:
  2. // #include <algorithm>

  3. // you can write to stdout for debugging purposes, e.g.
  4. // cout << "this is a debug message" << endl;


  5. #include <algorithm>

  6. int help(vector<int> &a) {
  7.     int n = a.size();
  8.     vector<int> f,g;
  9.     f.resize(n);
  10.     f[0] = a[0];
  11.     int now = a[0];
  12.     for (int i = 1; i < n; ++i) {
  13.         now = max(now, a[i]);
  14.         f[i] = max(a[i] + f[i - 1], now);
  15.     }
  16.     g.resize(n);
  17.     g[n - 1] = a[n - 1];
  18.     int answer = a[n - 1];
  19.     for (int i = n - 2; i >= 0; --i) {
  20.         g[i] = max(g[i + 1], 0) + a[i];
  21.         answer = max(answer, g[i]);
  22.     }
  23.     for (int i = 1; i < n; ++i) {
  24.         answer = max(answer, g[i] - a[i] + f[i - 1]);
  25.     }
  26.     return answer;
  27. }

  28. int solution(vector<int> &A) {
  29.     // write your code in C++11
  30.     int answer = help(A);
  31.     reverse(A.begin(),A.end());
  32.     answer = max(answer,help(A));
  33.     return answer;
  34.    
  35. }
复制代码


本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

3

主题

2

精华

254

积分

高级会员

Rank: 3Rank: 3

积分
254
发表于 12-4-2014 05:25 PM | 显示全部楼层

感谢楼主分享
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表