Project Euler 149

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/ulCC
 */


package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=149
    public class Euler149 extends Sprite {
        private var _tf : TextField;
  
        public function Euler149() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            t(solve(2000));
            var g : int = getTimer();
            t((g - s) + " ms");
        }

        private function solve(M : int) : int
        {
            var sk : Array = new Array(M * M);
            var k : int;
            for(k = 1;k <= 55;k++){
                sk[k - 1] = (100003 - 200003 * k + 300007 * k * k * k) % 1000000 - 500000;
            }
            for(k = 56;k < M * M;k++){
                sk[k - 1] = (sk[k - 24 - 1] + sk[k - 55 - 1] + 1000000) % 1000000 - 500000;
            }
            
            var i : int, j : int;
            var a : Array, v : Number;
            var maxsum : Number = -500000 * M;
            // horizontal
            for(i = 0;i < M;i++){
                a = new Array(M);
                for(j = 0;j < M;j++){
                    a[j] = sk[i * M + j];
                }
                v = subsum(a);
                if(v > maxsum)maxsum = v;
            }
            
            // vertical
            for(i = 0;i < M;i++){
                a = new Array(M);
                for(j = 0;j < M;j++){
                    a[j] = sk[i + j * M];
                }
                v = subsum(a);
                if(v > maxsum)maxsum = v;
            }
            
            // diagupper
            for(i = 0;i < M;i++){
                a = new Array(M - i);
                for(j = 0;j < M - i;j++){
                    a[j] = sk[i + j * (M + 1)];
                }
                v = subsum(a);
                if(v > maxsum)maxsum = v;
            }
            // diaglower
            for(i = 1;i < M;i++){
                a = new Array(M - i);
                for(j = 0;j < M - i;j++){
                    a[j] = sk[i * M + j * (M + 1)];
                }
                v = subsum(a);
                if(v > maxsum)maxsum = v;
            }
            // anti-diagupper
            for(i = 0;i < M;i++){
                a = new Array(M - i);
                for(j = 0;j < M - i;j++){
                    a[j] = sk[M - 1 - i + j * (M - 1)];
                }
                v = subsum(a);
                if(v > maxsum)maxsum = v;
            }
            // anti-diaglower
            for(i = 1;i < M;i++){
                a = new Array(M - i);
                for(j = 0;j < M - i;j++){
                    a[j] = sk[i * M + M - 1 + j * (M - 1)];
                }
                v = subsum(a);
                if(v > maxsum)maxsum = v;
            }
            
            return maxsum;
        }
        
        private static function subsum(a : Array) : Number
        {
            var maxsum : Number = 0;
            var tailmaxsum : Number = 0;
            for each(var v : Number in a){
                tailmaxsum = tailmaxsum > 0 ? tailmaxsum + v : v;
                if(maxsum < tailmaxsum)maxsum = tailmaxsum;
            }
            return maxsum;
        }

	private function t(o : *) : void
	{
            _tf.appendText("" + o + "\n");
	}
    }
}