North Carolina does not have the most maintained roads of any state, they have "largest state maintained highway network in the United States."
This is a function of them choosing to maintain roads at the state level instead of the county level. If you look at road miles by state [0] regardless of the actual entity that maintains them, they are 16th.
[0] http://blog.cubitplanning.com/2010/02/road-miles-by-state/