通过删除不超过一个elemnent来找到连续子阵列的最大总和的最大值？ [英] Find the maximal of maximum sum of contiguous subarray by deleting no more than one elemnent?
问题描述
您将获得一个N个整数数组。
数组的最大总和是此数组的非空连续子数组元素的最大总和。例如，数组[1，-2,3，-2,5]的最大和是6，因为子阵列[3，-2,5]的总和是6，并且不可能实现更大的子阵列和。
现在你可以从给定的数组中删除不超过一个元素。你可以通过这样做得到的数组的最大可能最大总和是多少？
我试过的：
You're given an array of N integer numbers.
The maximal sum of the array is the maximal sum of the elements of a nonempty consecutive subarray of this array. For example, the maximal sum of the array [1, -2, 3, -2, 5] is 6 because the sum of the subarray [3, -2, 5] is 6 and it is impossible to achieve greater subarray sum.
Now you're allowed to remove no more than one element from the given array. What is the maximal possible maximal sum of the resulting array you can achieve by doing so?
What I have tried:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int t;
long int temp;
cin>>t;
while (t > 0)
{
long long int n;
cin>>n;
long long int a[n];
for(int i=0; i<n; i++)
cin>>a[i];
long long int maxStartIndex=0;
long long int maxEndIndex=0;
long long int maxSum=a[0];
for(int i=0;i<n;i++)>
{
if(maxSum>a[i])
{
maxSum=a[i];
}
}
long long int cumulativeSum= 0;
long int maxStartIndexUntilNow=0;
for (int currentIndex = 0; currentIndex < n;currentIndex++)
{
long long int eachArrayItem = a[currentIndex];
cumulativeSum += eachArrayItem;
if (cumulativeSum > maxSum)
{
maxSum = cumulativeSum;
maxStartIndex = maxStartIndexUntilNow;
maxEndIndex = currentIndex;
}
if (cumulativeSum < 0)
{
maxStartIndexUntilNow = currentIndex + 1;
cumulativeSum = 0;
}
}
if (maxStartIndex == maxEndIndex)
{
long long int xyz;
if ((maxEndIndex + 2) <= n-1 && a[maxEndIndex+1]<0)
{
int i=2;
xyz = maxSum;
for (int i=maxEndIndex+2; i<=n-1; i++)
{
if (a[i] < 0)
break;
maxSum = maxSum+ a[i];
}
temp = maxSum;
}
if ((maxStartIndex-2)>=0 && a[maxStartIndex-1]<0)
{
maxSum=xyz;
int i=2;
while(a[maxStartIndex-i]>0 && i>=0)
{
maxSum=maxSum + a[maxStartIndex-i];
i--;
}
cout<<maxSum<<"\n";
if (temp > maxSum)
{
maxSum=temp;
}
}
}
else
{
long long int min=a[maxStartIndex];
for(int i=maxStartIndex;i<=maxEndIndex;i++)
{
if(min>a[i]){min=a[i];}
}
if (min < 0)
{
maxSum = maxSum + (-min);
}
else
{
int flag=0;
if ((maxEndIndex + 2) <= n-1 && a[maxEndIndex+1] < 0 && a[maxEndIndex+2] > 0)
{
maxSum=maxSum + a[maxEndIndex+2];temp=maxSum;flag=1;
}
if((maxStartIndex-2)>=0 && a[maxStartIndex-1]<0 && a[maxStartIndex-2]>0)
{
if (flag == 1)
maxSum = maxSum - a[maxEndIndex+2];
maxSum = maxSum + a[maxStartIndex-2];
if (temp > maxSum)
maxSum = temp;
}
}
}
cout<<maxSum<<"\n";
t--;
}
return 0;
}
推荐答案
首先，您需要了解如何编写一个能够为任何数组提供最大总和的正确函数。
如果我们从样本输入开始
First you need to figure how to write a proper function that will give you the maximum sum for any array.
If we start with a sample input
1, -2, 3, -2, 5, -1
您可以使用笔和纸来计算每个序列的最大总和，如下所示
you can use pen and paper to calculate the maximum sum for each sequence like this
Start Index = 0
0 + 1 = 1
1 - 2 = -1
-1 + 3 = 2
2 - 2 = 0
0 + 5 = 5 <- max
5 - 1 = 4
Start Index = 1
0 - 2 = -2
-2 + 3 = 1
1 - 2 = -1
-1 + 5 = 4 <- max
4 - 1 = 3
Start Index = 2
0 + 3 = 3
3 - 2 = 1
1 + 5 = 6 <- max and also maximum for the whole array
6 - 1 = 5
Start Index = 3
0 - 2 = -2
-2 + 5 = 3 <- max
3 - 1 = 2
Start Index = 4
0 + 5 = 5
5 - 1 = 4 <- max
Start Index = 5
0 - 1 = -1 <- max
基本上你循环遍历数组以找到最大总和，然后你将起始索引增加1并找到下一个序列的最大值。
在代码中这可以通过双循环或递归。
这是递归变量
Basically you loop through the array to find the maximum sum, then you increment the start index by 1 and find the maximum for the next sequence.
In code this can be done either by a double loop or recursively.
This is the recursive variant
int FindMaxValue(int* a, int len, int startIndex, int maxSum)
{
if (startIndex == len) // Exit condition
return maxSum;
int currentMaxSum = maxSum;
int tempSum = 0;
for (int i = startIndex; i < len; i++)
{
tempSum += a[i];
if (tempSum > currentMaxSum )
currentMaxSum = tempSum;
}
// Increment the start index for each iteration
return FindMaxValue(a, len, startIndex + 1, currentMaxSum);
}
在你的main（）中你调用这样的函数：
In your main() you call the function like this:
int maxSum = FindMaxValue(a, n, 0, INT_MIN);
printf("Max sum: %d\r\n", maxSum);
下一个任务是删除数组中的一个数字并找到新数组的最大值。
最简单的方法是使用另一个循环，每次迭代排除一个数字。
这需要对FindMaxValue（）进行少量修改，其中添加要跳过的索引。
The next task is to remove one of the numbers in the array and find the maximum value for the new array.
The easiest way to do this is to use yet another loop and exclude one number per iteration.
This requires a small modification of FindMaxValue() where you add the index you want to skip.
int FindMaxValue(int[] a, int len, int startIndex, int maxSum, int skipIndex)
{
if (startIndex == len)
return maxSum;
int currentMaxSum = maxSum;
int tempSum = 0;
for (int i = startIndex; i < len; i++)
{
if (i == skipIndex)
continue;
tempSum += a[i];
if (tempSum > currentMaxSum )
currentMaxSum = tempSum;
}
return FindMaxValue(a, len, startIndex + 1, currentMaxSum, skipIndex);
}
在主函数中添加一个新循环
Add a new loop in the main function
int maxSum = 0;
for (int i = 0; i < a.Length; i++)
{
maxSum = FindMaxValue(a, n, 0, INT_MIN, i);
printf("Index = %d -> Max Sum = %d\r\n", i, maxSum);
}
如果你想得到实际的序列，你必须自己做。
最后，此代码无法飞行
If you want to get the actual sequence, you have to do that yourself.
At last, this code will not fly
long long int a[n];
you必须动态分配内存
you have to allocate memory dynamically
int* a = (int*)calloc(n, sizeof(int));
并且不要忘记在代码末尾释放分配的内存
and don't forget to release the allocated memory at the end of the code
free(a);
此外，还不确定是谁告诉你需要声明一个 long long int 。这对你在这里展示的要求来说太过分了。
Also, not sure who gave you the idea that you need to declare a long long int. That is just overkill with the requirements you show here.
这是一个持续竞赛的问题！
见这里： 比赛页面| CodeChef [ ^ ]
实际上存在一个O（n）解决方案，但我不会在比赛结束前发布它！
This is a question from an ongoing contest!
See here: Contest Page | CodeChef[^]
Actually there exists an O(n) solution but I am not gonna post it before the end of the contest!
我们不做你的作业：这是有原因的。它就是为了让你思考你被告知的事情，并试着理解它。它也在那里，以便您的导师可以识别您身体虚弱的区域，并将更多的注意力集中在补救措施上。
亲自尝试，你可能会发现它不是和你想的一样困难！
如果遇到具体问题，请询问相关问题，我们会尽力提供帮助。但我们不打算为你做这一切！
We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.
Try it yourself, you may find it is not as difficult as you think!
If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!
这篇关于通过删除不超过一个elemnent来找到连续子阵列的最大总和的最大值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
