Average of analogRead goes below 0

I have the following code to get the average of a analog reading:

#define AVG_N 100

int values[AVG_N]; 
int val_index = 0;

void setup() {
  Serial.begin(9600);
  pinMode(A0, INPUT);
}

void loop() {
  int val = analogRead(A0);

  values[val_index++ % AVG_N] = val;
  int average = 0;
  for (int i = 0; i < AVG_N; i++) {
    average += values[i];
  }

  average /= AVG_N;
  Serial.print(val);
  Serial.print(" ");
  Serial.print(average);
  Serial.print(" ");
  Serial.println(0);
  delay(10);
}

Sometimes the average is a negative number, here is an example of the output:

270 313 0
612 317 0
612 320 0
271 320 0
612 323 0
611 327 0
612 -324 0
271 -324 0
270 -324 0
269 -324 0
271 -324 0
270 -324 0
612 -321 0

What is causing this?

int average = 0;

What range of values can an int data type hold? The answer is -32768 to 32767. If the average accumulates a number higher than 32767 it "rools over" to -32768. See the problem? Make average a long data type or better yet, unsigned long (because it should never go negative).

How large does val_index++ get to before you reset it?

Paul