LM35 Temperature Sensor Giving Inverted Readings

I have an LM35DZ sensor connected to an Arduino MEGA.
When I warm up the sensor, the value given by AnalogRead goes down, and when I cool down the sensor the value goes up.

With the sensor connected directly to +5V, Pin0, and GND I was getting very noisy values. After reading other posts and experimenting, I found that putting a resistor & capacitor in series between Vout and GND stabilised the readings (Values 500Ω & 0.01uF as that's what I had on hand)
The sensor & other components are on a breadboard, connected to the Arduino by short (less than 10CM) wires.
The Arduino is powered by a 12V supply, though USB is still connected for the serial output.

I thought it might be an issue with my code, so I reduced it down to the simplest possible based on Arduino Playground - LM35HigherResolution and I'm still getting the same results

int reading;
int tempPin = 0;

void setup() {
    analogReference(INTERNAL1V1); //ArduinoMEGA Internal 1.1V reference
    Serial.begin(9600);
}

void loop() {
    reading = analogRead(tempPin);
    Serial.println(reading);
    delay(1000);
}

Could you provide an schematic diagram showing how you connected the sensor to arduino?

Be sure you have the LM35 pins connected correctly, here's a datasheet.

float reading;
int tempPin = 0;

void setup() {
    analogReference(INTERNAL1V1); //ArduinoMEGA Internal 1.1V reference
    Serial.begin(9600);
}

void loop() {
    reading = analogRead(tempPin) * 1.1 / 1024 * 100;
    Serial.println(reading,1);
    delay(1000);
}

And is this definitely a genuine LM35?

@alesam see attached (sorry for the bad MSpaint drawing, I don't have access to anything better right now)

@outsider I've checked the pins, definitely wired correctly according to the datasheet.

@MarkT They came from a chinese seller on eBay, how would I check if they're genuine or not?

LM35.png

Looking at the flat side with pins pointed down, they should be (left to right) V+, Vout, V-, is that what you have?

outsider:
Looking at the flat side with pins pointed down, they should be (left to right) V+, Vout, V-, is that what you have?

Yep

gutyex:
@MarkT They came from a chinese seller on eBay, how would I check if they're genuine or not?

Compare printing with a genuine part, the font and layout may differ somewhat.

You cannot be sure about any parts from eBay, although they may be fine, sometimes they are not.

MarkT:
Compare printing with a genuine part, the font and layout may differ somewhat.

You cannot be sure about any parts from eBay, although they may be fine, sometimes they are not.

They look the same as all the photos that google images returns for "LM35DZ", but if I connect them directly to 5V and GND on the arduino then measure the voltage between Vout & GND with the my multimeter I get less than 10mV regardless of temperature, so I'm inclined towards them being fakes or a bad batch. I've ordered some more from a different seller so I'll see how those work out.