I'm a complete amateur and this post is just to share my personal experience.
For me, this is a great question from
@IGoddard! A wonderful piece of music too!
I've just listened to it and I would be unable to improvise any kind of of melody to these chords without playing a lot of 'wrong notes' along the way. I really love the richness of the chords and the changes . This richness makes it difficult for me to anticipate (when playing along) what's coming up from just a couple of listenings.
I'm not really much into music or jazz theory. I'd be a better soloist if I was, but where possible I prefer to (literally) just play it by ear. "Can’t help lovin dat man" is way beyond my abilities to improvise on the fly. So I'd write out the chord sequence in advance too and try to find a basis for a melody/improv.
I completely agree with
@jbtsax's advice to look for 'common notes' between adjacent chords and to pay attention to 7th, 4th notes etc. (I should follow his advice more often

).
I don't know whether this makes much sense but what works best for me is a combination of listening, chord analysis and then just playing around on the sax to find additional notes that fit and don't fit (usually during BigBand rehearsals) . For me personally, all of these are necessary to find something that works.
'Active Listening' to each section over and over again gives me an idea of the 'shape' of each section. Without even knowing exactly which chords are being played, it gives me an idea of where the 'tonic', dominant' 'subdominant' , 'relative minor' chords (and other intervals) fall and how they sound relative to each other. For me, it's like remembering a sentence structure. At this stage, I'm not looking for notes, I'm just listening to the basic 'structure' (what I call the 'shape') of each section. Long ago, I used to play guitar which helps me visualise (in basic keys) what the relationship is between the chords I hear. I think it's worth becoming familiar with the 'scale degrees' of chords so that you gradually learn to recognise chords relative to each other just by listening. Maybe you already do.
The 'shape' and 'sound' of each section becomes much more explicit when you map out the actual chord sequence. The 'added value' of listening for me is that l see the chords while remembering the 'shape' of the section. They add detail to what I already know rather than being an abstract set of symbols. I'm sure lots of people can look at chord symbols and 'hear' the chords in their heads. There's no rule about whether to listen first or map out the chords first and listen from this. Generallly, I prefer to just listen first.
Applying
@jbtsax's advice, I usually try to find the basis for a 'safe' melody/improv that doesn't sound wrong. Then I play around on the sax with a backing track to experiment with addititional notes/variations. I remember the ones that sound OK I and incorate these into my melody/solo. The ones that just sound wrong
I remember too and I make a mental note to avoid these.
I think that there's a balance to be found between 'analysis' and 'experimentation'. Ongoing 'analysis' when playing can easily to 'paralysis' which stifles expression and enjoyment. My motto is 'better a few wrong notes when playing freely than being afraid to stray from what's safe'. But the more you've learned about 'what's safe' and the variations that work and don't work, the fewer wrong notes you play. The key to this is preparation (listening, analysis, experimentation).
Hope this helps.
Mike