This is a good example of an image where the new dehaze filter from Lightroom 6 works wonders, as the lack of contrast is due to the atmospheric haze on the sea. Here's what I made out of the JPEG:
First I corrected the overall exposure by +1 EV, then I played a bit around with both clarity and the dehaze slider to find the best combination, and settled at +50 for both. Finally I adjusted the black (-40) and white (+20) sliders and applied some sharpening. Moreoever, I used the structure at the center of the platform as a grey card to get rid of a slight purple color cast. As you may notice, both dehaze and clarity tend to emphasize vignetting in the image, so it is important to properly correct for the vignetting first. Straightening the horizon and applying proper sharpening is also crucial for this image.
You can see that there are much more details to the sky and sea than in yours and Teds rendition.
As usually the case in post-processing, it is important to exercise restraint and not to carry the use of filters and tonal adjustments to the extreme in order to maintain a natural look and the atmosphere of the image. Simply expanding the histogram to the maximum wouldn't work here. However, I see that both of you did a good job in that regard and I couldn't have done better without the dehaze tool.