Click here to Skip to main content
15,867,308 members
Please Sign up or sign in to vote.
1.00/5 (4 votes)
See more:
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:

C++
#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;
}
Posted
Updated 30-May-16 15:03pm
v7
Comments
George Jonsson 29-May-16 5:22am    
Please show us the code you have written so far explain where you are stuck.
George Jonsson 29-May-16 5:43am    
Please, please use Improve question and insert your code there.
And formatted properly too.
Member 12552651 29-May-16 6:02am    
Done
George Jonsson 29-May-16 6:07am    
But not formatted with the correct language. It makes reading the code so much easier, and your job is to make it easy to help you.
Member 12552651 29-May-16 6:44am    
Done.Now help me out

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

C#
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


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
C++
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);
}

In your main() you call the function like this:
C++
int maxSum = FindMaxValue(a, n, 0, INT_MIN);
printf("Max sum: %d\r\n", maxSum);


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.
C++
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
C++
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
C++
long long int a[n];

you have to allocate memory dynamically
C++
int* a = (int*)calloc(n, sizeof(int));

and don't forget to release the allocated memory at the end of the code
C++
free(a);

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.
 
Share this answer
 
v2
Comments
Member 12552651 30-May-16 6:32am    
Can it be more effiecient. I mean to find sum by skipping one element in above question.getting TLE with above aproach.Input size is upto 10^5 and above mentioned is a O(n^2) approach.
George Jonsson 30-May-16 6:40am    
It can probably be much more efficient, but I don't want to spoil all the fun for you.
It is your task after all.
Member 12552651 30-May-16 21:24pm    
I have tried to skip only negative numbers.Thecomplexity is better than 0(n^2) but still getting TLE.Any help
George Jonsson 30-May-16 21:38pm    
I have kind of given you a lot of help already.
Now you start to talk about algorithm efficiency, that was not in the original question.
Look at ppolymorphe's Solution 4. It will boost the algorithm somewhat. You just need to add a few if-statements.
However, we don't know your time limit or what the true input data is.
Philippe Mori 31-May-16 18:13pm    
I vote 4 because your code probably works but is far from optimal...

Well I'm not too sure as by reading the link in solution 5, I realize that I misunderstood second part. I was thinking that you only need to remove 1 item to the original array but it seems that you still have to find the maximal sequence after that...
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!
 
Share this answer
 
Comments
George Jonsson 31-May-16 8:29am    
Thanks for the info.
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!
 
Share this answer
 
Comments
Member 12552651 29-May-16 5:32am    
Its not a homework.I just required an algorithm.I can do the rest job.Thank You
Philippe Mori 31-May-16 18:20pm    
As shown in solution 5, this is a contest... So it is even worst! You would try to pretend to be smart by asking other people to solve the problem. This is not honest at all.
The solution is brut force !
If the list is only negative numbers, the answer is the single element with maximum value.
If some elements a positive, you have to check every possible sublist.
in each sublist:
- reject the sublist if first or last element is negative.
- find the element with most negative value
- calc the sum of elements minus the negative one.
- compare with best answer so far and set this sublist as answer if better.

[Update]
Basically, testing every sublist is already O(n^2), thus your goal of O(n) algorithm will be complicated to achieve. A clever programming can improve the runtime, but you will stay on O(n^2).
 
Share this answer
 
v2
Comments
Member 12552651 30-May-16 21:29pm    
Will it be effiecient? I think its still 0(n^2).
Patrice T 30-May-16 22:16pm    
I fear there is no O(n) solution to this problem.
So O(n^2) is not so bad.
Philippe Mori 31-May-16 18:38pm    
Given that it is a contest (see solution 5), you are not honest to ask help to other people and you should be ashamed of yourself. As such, I am glad that no once give a really good solution.
Patrice T 31-May-16 19:30pm    
No need to flood the comments.
The contest is over and one can see other submissions.
1 comment under the question would have been enough.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900