0

I have a project in which I have to store some values and return some results based on them. The results and stored values are all integers. I have made every variable a long long int so that it will definitely fit the numbers (the array could be as long as 1000000). While I get totally normal values on up to 400000 numbers stored and I get them in low time (0.25 seconds), on 500000 the program just fails to execute. If my antivirus is on, it will even delete the executable file once I try to build or run it. On build though, the program itself will not show any syntax errors. Any ideas?

Code below:

#include <iostream>
#include <fstream>
using namespace std;
int main() {
  ifstream TextIn;
  ofstream TextOut;
  long long int N, i=1, sum=0;
  TextIn.open("share.in", ios::in);
  TextIn >> N;
  long long int A[N];

  for (i=1; i<=N; i++) {
    TextIn >> A[i];
    sum=sum+A[i];
  }

  TextIn.close();
  long long int sum1c2=0, sum1c1=0;
  i=0;

  do {
    i=i+1;
    sum1c1=sum1c1+A[i];
  } while ((sum1c1<=2+sum/3) && (i<N-2));

  sum1c2=sum1c1-A[i];
  long long int sum2c1c1=0, sum2c1c2=0, sum2c2c1=0, sum2c2c2=0, j=i-1;

  do {
    j=j+1;
    sum2c1c1=sum2c1c1+A[j];
  } while ((sum2c1c1<=2+sum/3) && (j<N-1));

  sum2c1c2=sum2c1c1-A[j];
  j=i;

  do {
    j=j+1;
    sum2c2c1=sum2c2c1+A[j];
  } while ((sum2c2c1<=2+sum/3) && (j<N-1));

  sum2c2c2=sum2c2c1-A[j];
  long long int sum3c1, sum3c2, sum3c3, sum3c4;
  sum3c1=sum-sum1c1-sum2c2c1;
  sum3c2=sum-sum1c1-sum2c2c2;
  sum3c3=sum-sum1c2-sum2c1c1;
  sum3c4=sum-sum1c2-sum2c1c2;
  long long int max1=0, max2=0, max3=0, max4=0;

  if (sum1c1>sum2c2c1) {
    if (sum1c1>sum3c1){
      max1=sum1c1;
    } else {
      max1=sum3c1;
    }
  } else {
    if (sum2c2c1>sum3c1) {
      max1=sum2c2c1;
    } else {
      max1=sum3c1;
    }
  }
  if (sum1c1>sum2c2c2) {
    if (sum1c1>sum3c2) {
      max2=sum1c1;
    } else {
      max2=sum3c2;
    }
  } else {
    if (sum2c2c2>sum3c2) {
      max2=sum2c2c2;
    } else {
      max2=sum3c2;
    }
  }
  if (sum1c2>sum2c1c1) {
    if (sum1c2>sum3c3) {
      max3=sum1c2;
    } else {
      max3=sum3c3;
    }
  } else {
    if (sum2c1c1>sum3c3) {
      max3=sum2c1c1;
    } else {
      max3=sum3c3;
    }
  }
  if (sum1c2>sum2c1c2) {
    if (sum1c2>sum3c4) {
      max4=sum1c2;
    } else {
      max4=sum3c4;
    }
  } else {
    if (sum2c1c2>sum3c4) {
      max4=sum2c1c2;
    } else {
      max4=sum3c4;
    }
  }

  long long int final_max;
  if (max1<=max2 && max1<=max3 && max1<=max4) {
    final_max = max1;
  } else if (max2<=max1 && max2<=max3 && max2<=max4) {
    final_max = max2;
  } else if (max3<=max1 && max3<=max2 && max3<=max4) {
    final_max = max3;
  } else {
    final_max = max4;
  }

  TextOut.open("share.out", ios::out);
  TextOut << final_max;
  TextOut.close();
  return 0;

}
Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
DGounaris
  • 182
  • 9

3 Answers3

4

You cannot declare an array with runtime size on the stack without using a compiler extension. So long long int A[N]; is illegal.

That being said with a 500000 element array, you are likely to hit a stack overflow. You should instead do something like

TextIn >> N;
std::vector<long long int> A(N);
for (long long int i = 1; i < N; ++i)
{
    TextIn >> A[i];
    sum += A[i];
}
TextIn.close();

The reason this will help is that even though the vector A is declared on the stack, the underlying memory is allocated from the heap, which has much more memory available than the stack.

Community
  • 1
  • 1
Cory Kramer
  • 114,268
  • 16
  • 167
  • 218
  • The loop should go from 0 to < N. – Peter Goldsborough Feb 17 '15 at 20:26
  • Firstly, thanks for the solution (and thanks to the others who mentioned it as well), using a vector fixed the problem. That being said, the problem didn't seem to be declaring A[N], but using too much memory on the array, since declaring A[1000000] had the same effect. Followup question: I have read that it doesn't matter where the "used" array cells are, as long as they are next to each other. Isn't that the case? So could I possibly have an array of A[N+1] cells (N isn't variable, just for generalization) and use for(i=1; i<=N; i++)? – DGounaris Feb 17 '15 at 21:45
1

Creating arrays in C++ using runtime values as the number of entries in the array is not legal C++. Some compilers can do this using an extension, but it still means that the code is using non-standard C++ syntax.

To get around this issue, plus more than likely solve your problem, use std::vector instead of arrays:

TextIn >> N;
std::vector<long long int> A(N);

The second issue is that you have at least one memory overwrite in your program:

for (i=1;i<=N;i++)
{
    TextIn >> A[i];
    sum=sum+A[i];
}

Arrays are indexed in C++ start from 0, not 1 and go to n-1, where n is the total number of entries. So the loop above should be:

for (i=0;i <N; i++)
{
    TextIn >> A[i];
    sum=sum+A[i];
}
PaulMcKenzie
  • 34,698
  • 4
  • 24
  • 45
0

Without having looked at your code I would say that 500000 integers is a very large number. Lets assume 8 bytes per integer(Which I believe is the minimum size of a long long).

500000*8 == 4000000 bytes or 4 megabytes, which is probably close to, if not, the size of your program's stack.

Solution: try using heap memory if you are going to be storing that amount of data.

Although this may not be the problem, especially if the antivirus flags it up(Which seems very strange to me). And if this was the case your program would segfault.

tom
  • 354
  • 4
  • 15