0

I am solving a problem in which I have to find those element from the array whose total gives maximum sum. But there is a condition that no two adjacent element can be the part of that max subarray. Here is my code using simple brute Force solution-

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t != 0)
    {
        int n, i, s, k = 0, m = -1001;
        vector< int > a;
        cin >> n;
        a.resize(n, 0);
        vector< int > b;
        for (i = 0; i < n; i++)
        {
            cin >> a[i];
            m = max(m, a[i]);
            if (a[i] < 0)
            {
                a[i] = 0;
                ++k;
            }
        }
        if (k == n)
            cout << m;
        else
        {
            k = 0;
            s = a[0];
            b.push_back(a[0]);
            for (i = 1; i < n; i++)
            {
                if (i != k + 1)
                {
                    if (a[i])
                    {
                        s += a[i];
                        b.push_back(a[i]);
                        k = i;
                    }
                }
                else
                {
                    if (s - a[i - 1] + a[i] > s)
                    {
                        b.pop_back();
                        s -= a[i - 1];
                        s += a[i];

                        b.push_back(a[i]);

                        ++k;
                    }
                }
            }
        }
        cout << endl;
        for (i = n; i >= 0; i--)
        {
            if (b[i])
                cout << b[i] << " ";
        }
        cout << endl;
        --t;
    }
    return 0;
}

Here is input to code- First line represent no. of test cases, Second line represent size of array And the next line shows array elements.m

5
5
-1 7 8 -5 4 
4
3 2 1 -1 
4
11 12 -2 -1 
4
4 5 4 3 
4
5 10 4 -1

Output-

4 8 
32 32607 -787829912 1 3 
32 32607 -787829912 12 
3 5 
10

Expected output-

4 8
1 3
12
3 5
10

So, there are 5 test cases. For the first test case and last two test case output is correct. But for second and third test case it is giving garbage value. What is the problem, that for some test cases it is giving garbage value, and for other not.

Robert Andrzejuk
  • 5,076
  • 2
  • 22
  • 31
T.g
  • 169
  • 2
  • 11
  • 2
    Unrelated: Do not use `#include `([why](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)) and avoid using `using namespace std;` ([why](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)). Together they reinforce teach other's worst effects and can result in truly nasty and inscrutable errors. – user4581301 Apr 08 '19 at 15:24
  • Yeah, please split the code into 4 functions: read in one test case, solve test case, print answer and the main function that does N loops. – Goswin von Brederlow Apr 08 '19 at 15:24
  • 2
    _What is the problem, that for some test cases it is giving garbage value, and for other not._ I would recommend to debug your code for the most minimal sample which produces garbage. – Scheff's Cat Apr 08 '19 at 15:25
  • My problem is why it's giving garbage value for third and second term case. If I change the order of test cases then also it gives garbage value for test case present at second and third position. – T.g Apr 08 '19 at 15:37
  • 1
    Seems like when you're printing, you should be iterating based on the size of `b` instead of `n`. I don't see what could insure that `b`'s size is `n`. Maybe you intended for `if (b[i])` to check if `b` has an `i`th element? It's instead checking if that element is zero, even if it doesn't exist (which is Undefined Behavior). – François Andrieux Apr 08 '19 at 15:47
  • 1
    Change your access from `a[i]` to `a.at(i)` for all `a` and `b`, and then you'll see the out of range exception when you exceed your vector size. – Eljay Apr 08 '19 at 15:51
  • You are emplacing no more than `n` elements into `b`, yet you iterate from `n` to `0` (which is `n+1` indices). Thus you are accessing `b` out of bounds for `i == n`, which is undefined behavior. – Max Langhof Apr 08 '19 at 16:23
  • @Max Langhof I have changed loop condition but still it's giving garbage value. In early case it was giving 3 garbage value but now it's giving 2 garbage value in both test cases. – T.g Apr 08 '19 at 16:30
  • Also, your algorithm doesn't correctly implement brute force. You cannot solve the input `1 2 4` correctly without backtracking. – Max Langhof Apr 08 '19 at 16:30
  • @T.g So what is your new loop condition? Do you check the size of `b` (you have to!)? – Max Langhof Apr 08 '19 at 16:31
  • @Max Langhof I have simply replaced n by n-1 in my loop – T.g Apr 08 '19 at 16:33

2 Answers2

1
    for (i = n; i >= 0; i--)
    {
        if (b[i])
            cout << b[i] << " ";
    }

This prints out n+1 values in b. But even in the best case, b only has n values (for n=1). And for n>1, b.size() is less than n, so you are reading garbage from outside the vector's storage (this is undefined behavior). Just use the correct bound:

for (i = b.size() - 1; i >= 0; ++i)
Max Langhof
  • 23,383
  • 5
  • 39
  • 72
  • Thanks, it's working. But my doubt is still unclear. Why only for second and third test case not for all. – T.g Apr 08 '19 at 16:46
  • First off, it's **undefined behavior**. For all you know your computer could halt and catch fire. That said, you are reading uninitialized memory. If you're "lucky" you will find `0`s there and your check will make it _look_ like everything is fine. Remove the `if (b[i])` and you will find that it always prints too many values (obviously). But sometimes you are "unlucky" and the random memory you read is not zeros. If you want any more detail you can look at the generated assembly and reason about that, everything else is very pointless. – Max Langhof Apr 08 '19 at 16:51
0

I think I found your (first) problem:

if(k==n)
cout<<m;

When all numbers are negative this outputs the largest of them.

But the empty array has a sum of 0 and is larger than a negative number and has no 2 adjacent members in it. So clearly the right answer should be 0, not m.

Goswin von Brederlow
  • 11,875
  • 2
  • 24
  • 42
  • Sorry, but my problem is why it is giving garbage value in the second and third test cases. – T.g Apr 08 '19 at 15:33