The first stop for me would be to optimise and obfuscate the code with ProGuard which is known to work with byte code targeted at Android’s Dalvik VM (via Dex). It’s a really great tool and can increase the difficulty of ‘reversing’ your code while shrinking your code’s footprint (in some cases dramatically: a recent applet of mine went from about 600 KB down to about 50 KB).
Like others are saying, you will never get 100% security of your algorithm’s details while its implementation is being distributed to clients. For that, you’d need to keep the code on your servers alone. Attempts to near 100% percent security for client code effectively amount to DRM and can make your client code fragile in the face of network outages and just generally frustrate (legitimate) users.
The Android developers blog has some useful articles on the matter of ‘tamper resistant’ Android apps (and they recommend the use of ProGuard as part of the overall approach).
With regards to ‘creative’ approaches: some developers employ debugger detection techniques to prevent run-time analysis and combine this with encryption of portions of binary code (to deter static analysis), but to be honest, a determined enough attacker can circumvent these, while it can cause legitimate user frustration as illustrated by the Windows KB article Games: Error Message: A Debugger Has Been Detected: Unload the Debugger and Try Again. My girlfriend’s ‘Learn to drive’ DVD software will not run under VirtualBox for this reason, but she blames Linux of course!
OpenRCE and Wikipedia’s article on obfuscated code may be good starting points if you want to look into this further. But be warned, you may lose more through over zealous use of these techniques frustrating your users than you would through loss of trade secrets by reverse engineering. Like Anton S says, maybe the most ‘creative’ approach lies with tweaking the business model rather than the technology.
The latest Android SDK update on 6th Dec 2010 (coinciding with Android 2.3 Gingerbread release):
Integrated ProGuard support: ProGuard is now packaged with the SDK Tools. Developers can now obfuscate their code as an integrated part of a release build.