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

MaxSliceSum

5 -7 3 5 -2 4 -1

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

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

Blocks题解(区间dp)

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

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