查找数组中元素的最大总和（扭曲）

Question

给定一个包含 +ve 和 -ve 整数的数组，找出不允许跳过 2 个连续元素的最大总和（即你必须 select 至少其中一个才能向前移动） .

例如：-

10, 20, 30, -10, -50, 40, -50, -1, -3

输出：10+20+30-10+40-1 = 89

Answer 1

使用可以解释这一点的重复：

dp[i] = max(dp[i - 1] + a[i], <- take two consecutives
            dp[i - 2] + a[i], <- skip a[i - 1])

基本案例留作练习。

Answer 2

回答：

我认为这个算法会有所帮助。

1. 创建一个方法，输出特定用户输入数组的最大总和，比如 T[n]，其中 n 表示总数。的元素。
2. 现在这个方法将继续添加数组元素，直到它们为正。因为我们想要最大化和并且没有必要放弃正元素。
3. 一旦我们的方法遇到一个负数元素，它会将所有连续的负数元素转移到另一个方法，该方法创建一个新数组 N[i] 这样这个数组将包含我们在 T[n] 中遇到的所有连续的负数元素] 和 returns N[i] 的最大输出。
通过这种方式，我们的主要方法不会受到影响，它会继续添加正元素，每当遇到负元素时，它不会添加它们的实际值，而是添加该连续负元素数组的净最大输出。

例如：T[n] = 29,34,55,-6,-5,-4,6,43,-8,-9,-4,-3,2,78 //这里 n=14

主要方法工作：

29+34+55+（发送数据并从数组 [-6,-5,-4] 的辅助方法获取值）+6+43+（发送数据并从数组 [-8,-9] 的辅助方法获取值,-4,-3])+2+78
进程以最大输出终止。

辅助方法工作：
{

N[i] = 在需要时从 Main 方法或本身获取数组。这基本上是一种递归方法。
假设 N[i] 有 N1、N2、N3、N4 等元素。

对于我> = 3：
现在选择是这样的。
1. 如果我们采用 N1，那么我们可以递归左边的数组，即 N[i-1]，它具有除 N1 以外的所有元素，顺序相同。这样净最大输出将是
N1+（递归地发送数据并从数组 N[i-1] 的辅助方法中获取值）
2.如果我们不拿N1，那么我们就不能跳过N2。所以，现在算法就像第一个选择，但从 N2 开始。所以在这种情况下的最大输出将是
N2+（递归地发送数据并从数组 N[i-2] 的辅助方法中获取值）。这里 N[i-2] 是一个数组，包含除 N1 和 N2 之外的所有 N[i] 元素，顺序相同。
终止：当我们只剩下大小为 1 的数组（对于 N[i-2] ）时，我们必须选择该特定值作为不可选项。
递归最终将产生最大输出，我们必须最终选择那个选择的输出是更多的。并将最大输出重定向到需要的地方。

对于我=2：
我们必须选择更大的值

对于我=1：
我们当然可以跳过那个值。
所以在这种情况下最大输出将为 0。

}

Answer 3

如果您看到 +ve 整数，请将其添加到总和中。如果您看到一个负整数，则检查下一个最大的整数并将其添加到总和中。

10, 20, 30, -10, -50, 40, -50, -1, -3

为此添加 10, 20, 30, max(-10, -50), 40 max(-50, -1) 并且因为 -3 旁边没有元素，所以丢弃它。

如果最后一个元素为 +ve，则将求和。

Answer 4

我觉得这个回答对你有帮助。

给定数组：

Given:- 10 20 30 -10 -50 40 -50 -1 -3

Array1:-10 30 60  50  10 90  40 89 86

Array2:-10  20 50  40  0  80  30 79 76

取array1[n-1],array1[n],array2[n-1],array2[n] i.e 89(array1[n-1])

的最大值

算法：-

为数组 1 赋值 rray1[0]=a[0],array1=a[0]+a[1] 和 array2[0]=a[0],array2[1]=a[1].
计算 array1 的值从 2 到 n 是 array1[i-1]+a[i] 或 array1[i-2]+a[i] 的总和的最大值。
```
for loop from 2 to n{    
    array1[i]=max(array1[i-1]+a[i],array1[i-2]+a[i]);

}
```
类似地，对于 array2，从 2 到 n 的值是 array2[i-1]+a[i] 或 array2[i-2]+a[i].
之和的最大值
```
for loop from 2 to n{    
 array2[i]=max(array2[i-1]+a[i],array2[i-2]+a[i]);    
}
```

终于找到array1[n-1],array[n],array2[n-1],array2[n]的最大值;

   int max(int a,int b){      
   return a>b?a:b;    
   }

   int main(){    
   int a[]={10,20,30,-10,-50,40,-50,-1,-3};    
   int i,n,max_sum;    
   n=sizeof(a)/sizeof(a[0]);    
   int array1[n],array2[n];    
   array1[0]=a[0];    
   array1[1]=a[0]+a[1];    
   array2[0]=a[0];    
    array2[1]=a[1];    

    for loop from 2 to n{    
    array1[i]=max(array1[i-1]+a[i],array1[i-2]+a[i]);    
    array2[i]=max(array2[i-1]+a[i],array2[i-2]+a[i]);

    }    
       --i;

    max_sum=max(array1[i],array1[i-1]);    
    max_sum=max(max_sum,array2[i-1]);    
    max_sum=max(max_sum,array2[i]);    

     printf("The max_sum is %d",max_sum);    
      return 0;    
    }

答：max_sum是89

Answer 5

public static void countSum(int[] a) {
        int count = 0;
        int skip = 0;
        int newCount = 0;

        if(a.length==1)
        {
            count = a[0];
        }
        else
        {
            for(int i:a)
            {
                newCount = count + i;
                if(newCount>=skip)
                {
                    count = newCount;
                    skip = newCount;
                }
                else
                {
                    count = skip;
                    skip = newCount;
                }
            }
        }
        System.out.println(count);
    }
}

Answer 6

这个问题可以用动态规划的方法来解决。

设arr为给定数组，opt为存储最优解的数组。 opt[i]是从第i个元素开始可以得到的最大和

opt[i] = arr[i] + (some other elements after i)

现在为了解决这个问题，我们向后迭代数组 arr，每次都存储答案 opt[i]。由于我们不能跳过 2 个连续元素，因此必须包含 element i+1 或 element i+2 在 opt[i].

所以对于每个 i，opt[i] = arr[i] + max(opt[i+1], opt[i+2])

看这段代码就明白了：

int arr[n];  // array of given numbers. array size = n.
nput(arr, n);   // input the array elements (given numbers)

int opt[n+2];   // optimal solutions. 
memset(opt, 0, sizeof(opt));    // Initially set all optimal solutions to 0.

for(int i = n-1; i >= 0; i--) {
    opt[i] = arr[i] + max(opt[i+1], opt[i+2]);
}

ans = max(opt[0], opt[1])   // final answer.

观察到 opt 数组有 n+2 个元素。这是为了避免访问opt[i+1]和opt[i+2][=时出现非法内存访问异常（内存越界） 41=] 对于最后一个元素 (n-1).

See the working implementation of the algorithm given above

Answer 7

令数组大小为 N，索引为 1...N

令 f(n) 为函数，它提供子数组 (1...n) 的最大总和的答案，使得没有两个剩余元素是连续的。

 f(n) = max (a[n-1] + f(n-2), a(n) + f(n-1))

在第一个选项中，即 - {a[n-1] + f(n-2)}，我们将保留最后一个元素，并且由于所给出的条件选择倒数第二个元素。

在第二个选项中，即 - {a(n) + f(n-1)}，我们选择子数组的最后一个元素，因此我们可以选择 select/deselect 倒数第二个元素.

现在从基本情况开始：

f(0) = 0   [Subarray (1..0) doesn't exist]

f(1) = (a[1] > 0 ? a[1] : 0);    [Subarray (1..1)]

f(2) = max( a(2) + 0, a[1] + f(1))   [Choosing atleast one of them]

向前迈进，我们可以计算任何 f(n)，其中 n = 1...N，并存储它们以计算下一个结果。是的，很明显，案例 f(N) 会给我们答案。

Time complexity o(n)
Space complexity o(n)

Answer 8

n = arr.length()。在数组末尾附加 0 以处理边界情况。 ans：大小为 n+1 的 int 数组。 ans[i] 将存储数组 a[0...i] 的答案，其中 a[i] 包含在答案总和中。现在，

ans[0] = a[0]
ans[1] = max(a[1], a[1] + ans[0])
for i in [2,n-1]: 
   ans[i] = max(ans[i-1] , ans[i-2]) + a[i]

最终答案是[n]

Answer 9

If you want to avoid using Dynamic Programming

要找到最大总和，首先，您必须将所有正数相加数字。
我们将只跳过负面元素。因为我们不是允许跳过 2 个连续的元素，我们将把所有 contiguous 临时数组中的负元素，并且可以计算出最大和使用下面定义的 sum_odd_even 函数的替代元素。
然后我们可以将所有此类临时数组的最大值添加到我们所有的总和中正数。最后的总和将为我们提供所需的输出。

代码：

def sum_odd_even(arr):
    sum1 = sum2 = 0
    for i in range(len(arr)):
        if i%2 == 0:
            sum1 += arr[i]
        else:
            sum2 += arr[i]
    return max(sum1,sum2)

input = [10, 20, 30, -10, -50, 40, -50, -1, -3]
result = 0
temp = []
for i in range(len(input)):
    if input[i] > 0:
        result += input[i]
    if input[i] < 0 and i != len(input)-1:
        temp.append(input[i])
    elif input[i] < 0:
        temp.append(input[i])
        result += sum_odd_even(temp)
        temp = []
    else:
        result += sum_odd_even(temp)
        temp = []

print result

Answer 10

简单的解决方案：扭曲跳过:)。如果连续 -ve，则跳过 i 和 i+1 中的最小数字。有 if 条件检查直到 n-2 个元素并检查最后一个元素。

int getMaxSum(int[] a) {
    int sum = 0;
    for (int i = 0; i <= a.length-2; i++) {
        if (a[i]>0){
            sum +=a[i];
            continue;
        } else if (a[i+1] > 0){
            i++;
            continue;
        } else {
            sum += Math.max(a[i],a[i+1]);
            i++;
        }
    }
    if (a[a.length-1] > 0){
        sum+=a[a.length-1];
    }
    return sum;
}

Answer 11

正确的重现如下：

dp[i] = max(dp[i - 1] + a[i], dp[i - 2] + a[i - 1])

第一种情况是我们选择第i个元素的情况。第二种情况是我们跳过第 i 个元素。在第二种情况下，我们必须选择第 (i-1) 个元素。

IVlad答案的问题是它总是选择第i个元素，这会导致答案不正确。

Answer 12

这个问题可以使用包含、排除方法来解决。

对于第一个元素，include = arr[0], exclude = 0。

其余元素：

nextInclude = arr[i]+max(include, exclude)

nextExclude = include 

include = nextInclude

exclude = nextExclude

最后，ans = Math.max(include,exclude)。

类似问题可参考(不一样)=> https://www.youtube.com/watch?v=VT4bZV24QNo&t=675s&ab_channel=Pepcoding.

查找数组中元素的最大总和（扭曲）

Find max sum of elements in an array ( with twist)

algorithm

logic

kadanes-algorithm