If you're just walking, forget it. If it's true that he went from 10k calories to 2k a day, then he could have done just about nothing and still lost a ton of weight. subway is in the business of selling sandwiches and they were capitalizing on something that is very much the exception, not the rule.
Vegetables and high quality meats and fish with ample amounts of natural fats (beef fat, butter, lard, cocoanut oil, olive oil) will get you a very long way. Avoid any and all refined carbs.
Subway = no-no
No grains, no potatoes, no juices, no booze and no junk food.
If you find yourself getting hungry all the time, get more fat in your diet. It's natures appetite suppressant and it won't make you gain weight. Carbs are the culprit leading to syndrome X, insulin resistance and eventual diabetes.
As a man, if your belly button circumference measures wider than your hip bones, you have insulin resistance.
Supplementing with L-Glutamine and taking Pancreatic enzymes can help get your body back on track, if you can stick to a paleo-esque diet of meats/fish, veggies and a bit of fruit (post workout).
Everyone is different. some can handle a bit more carbs than others. You need to tailor your intake by trying and seeing how you react. I don't do carbs very well. Bread and beer make me fat. Period. Some people can handle the occasional sandwich.