【题解】【数组】【DP】【Codility】MaxSliceSum & MaxDoubleSliceSum

MaxSliceSum

5 -7 3 5 -2 4 -1

这个数组的最大子串是3 5 -2 4

Complexity:

  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

思路

O(n) 的解法的关键,是把原来求最优的问题转化为一个具有最优子结构的问题,枚举最大字串的右边界,再在求解其各个子问题解的过程中取最大值。假设以第i个元素结尾的子序列的最大值是maxending,那么以第i+1个元素结尾的子序列的最大值是max(0, maxending+ a[i+1])

代码

int solution(const vector<int> &A) {
    if(A.size() == 0) return 0;
    int max_ending_i = 0;
    int max_slice = A[0];
    for(int i : A){
        max_ending_i = max(i, max_ending_i+i);
        if(max_ending_i > max_slice) max_slice = max_ending_i;
    }
    return max_slice;
}

MaxDoubleSliceSum

A non-empty zero-indexed array A consisting of N integers is given.

A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a?double slice.

The?sum?of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y ? 1] + A[Y + 1] + A[Y + 2] + ... + A[Z ? 1].

For example, array A such that:

?

 A[0] = 3 A[1] = 2 A[2] = 6 A[3] = -1 A[4] = 4 A[5] = 5 A[6] = -1 A[7] = 2

contains the following example double slices:

  • double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
  • double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 ? 1 = 16,
  • double slice (3, 4, 5), sum is 0.

The goal is to find the maximal sum of any double slice.

Write a function:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A consisting of N integers, returns the maximal sum of any double slice.

For example, given:

?

 A[0] = 3 A[1] = 2 A[2] = 6 A[3] = -1 A[4] = 4 A[5] = 5 A[6] = -1 A[7] = 2

the function should return 17, because no double slice of array A has a sum of greater than 17.

Assume that:

  • N is an integer within the range [3..100,000];
  • each element of array A is an integer within the range [?10,000..10,000].

Complexity:

  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

思路

  1. 乍一看这个要比最大子段和高级,似乎要枚举最大字串的右边界i和中间点center,但其实只用枚举右边界i,右边界从i-1变成i之后,中间点只可能是center或者i-1中的一个,中间点为k的时候左边界不变最优,中间点为i-1的时候需要求最优左边界(这就是个内嵌的MaxSliceSum问题);还有一种情况就是只保留A[i-1]一个元素。整体复杂度仍然是时间 O(N),空间 O(1)。
  2. 还有一种思路就是只枚举中间点k,分别算以k-1结尾和k+1开头的最大字段和,然后再把两者拼起来,这种方法整体复杂度是时间 O(N),空间 O(N)。

代码

int solution(vector<int> &A) {
    if(A.size() <= 3) return 0;
    int max_left = 0;//中间点为i-1右边界为i时左段最大值
    int max_ending = 0;//右边界为i时两段最大值
    int center = 1;//中间点
    int max_slice = 0;
    for(int i = 3; i< A.size(); i++){
        max_left = max(max_left+A[i-2], A[i-2]);//MaxSliceSum问题
        max_ending = max(max_ending+A[i-1], A[i-1], max_left);//MaxDoubleSliceSum问题
        if(max_ending == A[i-1]) center = i-2;
        else if(max_ending == max_left) center = i-1;
        if(max_ending > max_slice) max_slice = max_ending;
    }
    return max_slice;
}
inline int max(int a, int b, int c){
   if(b>a) a=b;
   if(c>a) a=c;
   return a;
}

【题解】【数组】【DP】【Codility】MaxSliceSum & MaxDoubleSliceSum

时间: 07-03

【题解】【数组】【DP】【Codility】MaxSliceSum & MaxDoubleSliceSum的相关文章

hdu 3030 Increasing Speed Limits (离散化+树状数组+DP思想)

Increasing Speed Limits Time Limit: 2000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 481    Accepted Submission(s): 245 Problem Description You were driving along a highway when you got caught by the road p

tyvj 1005 采药 0-1背包 优化的一位数组 dp 代码1

#include <iostream> #include <string.h> using namespace std; int dp[1005], w[105],v[105],T,M; int max(int x,int y) {    return x>y?x:y;   } void  f( ) {   int i,j; for (i=1; i<=M; i++) for (j=T;j>=0; j--) if (j>=w[i]) dp[j]=max(dp[

tyvj 1005 采药 0-1背包 优化的一位数组 dp 代码2

#include <iostream>#include <string.h>using namespace std;int dp[1005], w[105],v[105],T,M;int max(int x,int y){    return x>y?x:y;   }void  f( ){   int i,j;    for (i=1; i<=M; i++)        for (j=T;j>=w[i]; j--)          dp[j]=max(dp[j

tyvj 1005 采药 0-1背包 优化的一位数组 dp 代码3

#include <iostream>#include <string.h>using namespace std;int dp[1005], w,v,T,M;int max(int x,int y){    return x>y?x:y;   }void  f( ){   int i,j;    for (i=1; i<=M; i++)    {   cin>>w>>v;         //直接读进去        for (j=T;j>

hdu4455之树状数组+DP

Substrings Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1571    Accepted Submission(s): 459 Problem Description XXX has an array of length n. XXX wants to know that, for a given w, what is

[后缀数组+dp/AC自动机+dp+线段树] hdu 4117 GRE Words

题意: 给你N个字符串, N(1 <= N <= 2w), 所有串的长度加一起不超过30w.每个串有个值.这个值[-1000, 1000]. 问不打乱字符串顺序,从中取若干个字符串,使得前一个串是后一个串的子串,求满足前面调条件的字符串值得和最大,求这个值. 思路: 其实就是一个很明显的dp. dp[i]代表以第i个字符串结尾的最大权值. 但是就是子串这个问题怎么处理. 由于这题数据比较水可以用后缀数组处理这个问题. 将所有字符串拼接,做sa. 每次在height数组里往上和往下寻找公共前缀等

Blocks题解(区间dp)

Blocks题解 区间dp 阅读体验...https://zybuluo.com/Junlier/note/1289712 很好的一道区间dp的题目(别问我怎么想到的) dp状态 其实这个题最难的地方是这道题目的状态怎么设 首先既然是区间dp,那肯定最先想到的状态是 $dp[i][j]$表示消掉区间$[i,j]$上所有的块的最大分数 突然发现这个状态会受区间外和$i$或$j$颜色相同的块的影响 并且转移也并不好转移=_= 所以我们考虑换一种状态... 既然说会受到外面的块的影响?那考虑一种方法来

[CTSC2017]最长上升自序列(伪题解)(树状数组+DP套DP+最小费用最大流+Johnson最短路+Yang_Tableau)

部分分做法很多,但每想出来一个也就多5-10分.正解还不会,下面是各种部分分做法: Subtask 1:k=1 LCS长度最长为1,也就是说不存在j>i和a[j]>a[i]同时成立.显然就是一个LDS,树状数组直接求即可. Subtask 2:k=2 最多两个,也就是可以由两个LCS拼起来,f[i][j]表示第一个LCS以i结尾,第二个以j结尾的方案数,转移显然. Subtask 3:k=2 树状数组优化DP,复杂度由$O(n^3)$降为$O(n^2 \log n)$ Subtask 4,5:

POJ 3378 Crazy Thairs(树状数组+DP)

[题目链接] http://poj.org/problem?id=3378 [题目大意] 给出一个序列,求序列中长度等于5的LIS数量. [题解] 我们发现对于每个数长度为k的LIS有dp[k][i][a[i]]=dp[k-1][i-1][0~a[i]-1] 我们用5个树状数组维护不同长度的LIS,递推即可,注意答案超过LL,需要用大数. [代码] #include <cstdio> #include <algorithm> #include <cstring> usi