Yes, a map is a valid type for an array. Your particular schema is not legal however, as it should be
{
"name":"deviceids",
"type":"record",
"fields":[
{ "name": "arrayOfMaps",
"type":{
"type": "array",
"items":{
"type":"map",
"values":"string"
}
}
}
]
}
That is, the fields of your record must be named, and the type definition for array and map both have to be full definition giving both the outer complex type (map/array) and contained type.
Since it can be hard sometimes to answer specific Avro questions based on the available documentation and repository of examples, the easiest way to answer this sort of question is probably to just try to compile it using the Avro tools jar, which can be found alongside the regular jars in the Avro releases.
java -jar avro-tools-1.7.5.jar compile schema /path/to/schema .
This will quickly resolve the concern over whether or not it is valid. If this still doesn't resolve the issue, the Avro mailing lists seem fairly active.