具体最大萨姆 - C/C++

假设我们有一个数组：7 3 1 1 6 13 8 3 3 我必须找到这个阵列，使得最大总和：具体最大萨姆 - C/C++

如果我添加13的总和：我不能从每一侧添加相邻元件：6 1和8 3不能被添加到总和
我可以跳过一样多的元素必须使总和最大

我的算法是这样的：

我把数组的最大元素，并添加到总和
我作出这样的元素和相邻元素-1
我一直这样做，直到它不可能找到了最大

问题是，对于某些特定的测试用例，这种算法是错误的。让我们来看看这个例子：15 40 45 35

根据我的算法：

我拿45，使邻居-1
程序结束

做正确的方法它是15 + 35 = 50

来源

2013-12-15 Arlind

你的算法是什么？ –

...并且代码 –

在哪里我也很困惑。数组只有一个和，所以max = min = sum？ –

这个问题可以用dynamic programming来解决。

设A为阵，让DP[m]在{A[1]~A[m]}
最大总和一个的每一个元素只有两个状态，被加入到总和与否。首先我们假设我们已经确定了DP[1]~DP[m-1]，现在看{A[1]~A[m]},A[m]只有我们已经说过的两种状态，如果已经加入A[m]，A[m-1]和A[m-2]不能加入到总和中，所以在添加状态中，最大和是A[m]+DP[m-3]（意向：DP[m-3]一直是最大总和{A[1]~A[m-3]}），如果A[m]尚未加入的总和，最高金额为DP[m-1]，所以我们只需要比较A[m]+DP[m-3]和DP[m-1]，更大的是DP[m]。这个想法和数学归纳法是一样的。
所以DP方程为DP[m] = max{ DP[m-3]+A[m], DP[m-1] }，DP[size(A)]是结果

的复杂度为O（n），伪代码如下：

DP[1] = A[1]; 
DP[2] = max(DP[1], DP[2]); 
DP[3] = max(DP[1], DP[2], DP[3]); 
for(i = 4; i <= size(A); i++) { 
    DP[i] = DP[i-3] + A[i]; 
    if(DP[i] < DP[i-1]) 
     DP[i] = DP[i-1]; 
}

来源

2013-12-15 11:27:55 AImager

你能解释一下吗？ – Arlind

@Arlind，我编辑了我的答案，可以详细阅读第二点 – AImager

这是解决的一个动态规划方法，采取O（N）时间和O（N）空间。实施以下操作：

int max_sum(int pos){ 

    if(pos >= N){ // N = array_size 
     return 0; 
    } 

    if(visited(pos) == true){ // if this state is already checked 
     return ret[pos];  // ret[i] contains the result for i'th cell 
    } 

    ret[pos] = max_sum(pos+3) + A[pos] + ret[pos-2]; // taking this item 

    ret[pos] = max(ret[pos], ret[pos-1]+ max_sum(pos+1)); // if skipping this item is better 
    visited[pos] = true; 
    return ret[pos]; 
} 

int main(){ 
    // clear the visited array 
    // and other initializations 
    cout << max_sum(2) << endl; //for i < 2, ret[i] = A[i] 
}

来源

2013-12-15 12:23:42 Fallen

，上述问题是在具有在O（N）的动态规划溶液的路径图表最大独立集问题（与扭转）。

解决它递推关系： -

Max(N) = maximum(Max(N-3) + A[N] , Max(N-1))

说明： - 如果我们必须从N个元素中选择最大设定比我们既可以选择从第一N-3元件或我们设置第N个元素和最大可以从第N个元素以外的第N-1个元素中选择最大值。

伪代码： -

Max(1) = A[1]; 
Max(2) = maximum(A[1],A[2]); 
Max(3) = maximum(A[3],Max(2)); 

for(i=4;i<=N;i++) { 

Max(N) = maximum(Max(N-3)+A[N],Max(N-1)); 

}

来源

2013-12-15 12:33:40

至于建议，这是一个动态的规划问题。

首先，一些符号，设：

A是数组，整数，长度N
A[a..b)的是含有在索引a元素多达但不包括bA所述子集（半开间隔）。
M是一个数组，使得M[k]是A[0..k) 的具体最大总和，使得M[N]是我们原始问题的答案。

我们可以通过其关系描述的M（M[n]）的元素，以其中的k < nM（M[k]）一种或多种元素。这适用于一个很好的线性时间算法。那么这种关系是什么？

基座情况如下：
- M[0]是空列表，它必须是0的最大特定总和。
- M[1]是单个元素的最大特定总和，因此必须是那个元素：A[0]。
- M[2]是前两个元素的最大特定总和。只有两个要素，我们可以选择第一个或第二个，所以我们最好挑选两个较大的：max(A[0], A[1])。
现在，如果我们知道M[0..n)，那么我们怎么计算M[n]？那么，我们可以选择：要么我们添加A[n-1]（A[0..n)中的最后一个元素），要么我们不添加。我们不知道某些是否加入A[n-1]会为一笔较大，所以我们尽量都走最大：
- 如果我们不加A[n-1]将总和是什么呢？这与紧接在它之前的最大特定总和相同：M[n-1]。
- 如果我们做加A[n-1]然后我们不能有我们的解决方案中的前两个元素，但我们可以有任何元素之前，这些。我们知道，M[n-1]和 M[n-2]威力已经使用的那些前两个元素，但绝对M[n-3] 没有，因为它是在范围A[0..n-3)最大。所以我们得到 M[n-3] + A[n-1]。
我们不知道哪一个是更大的，虽然，（M[n-1]或M[n-3] + A[n-1]），所以要找到在M[n]最大的款额，我们必须考虑这两个的最大值。

所以关系变成：

M[0] = 0 
M[1] = A[0] 
M[2] = max {A[0], A[1]} 
M[n] = max {M[n-1], M[n-3] + A[n-1]} where n > 2

注意很多答案似乎忽略了空单的情况下，却是绝对是一个有效的输入，所以应占对于。

在C++解决方案的简单翻译如下：

（需要特别注意的一个事实，即m的大小比a大小一个更大）

int max_specific_sum(std::vector<int> a) 
{ 
    std::vector<int> m(a.size() + 1); 

    m[0] = 0; m[1] = a[0]; m[2] = std::max(a[0], a[1]); 

    for(unsigned int i = 3; i <= a.size(); ++i) 
     m[i] = std::max(m[i-1], m[i-3] + a[i-1]); 

    return m.back(); 
}

但是该实现具有线性空间要求的大小为A。如果你看看M[n]的定义，你会看到，它仅依靠M[n-1]和M[n-3]（和前面的元素列表全没有），这意味着你只需要存储以前的3种元素在M，导致恒定空间要求。（这个实现的细节留给OP）。

来源

2013-12-15 12:55:13 amnn

具体最大萨姆 - C/C++

回答

相关问题