maxsub.zig

const std = @import("std");
const FileOutStream = std.io.FileOutStream;
const sampleSize = 16;
const heap = std.heap.c_allocator;
const math = std.math;

var stdout : FileOutStream = undefined;

fn randomSample() ![sampleSize]i8 {
    var buf: [8]u8 = undefined;
    var samples: [sampleSize]i8 = undefined;

    try std.os.getRandomBytes(buf[0..]);
    const seed = std.mem.readIntLE(u64, buf[0..8]);
    var r = std.rand.DefaultPrng.init(seed);

    var i: usize = 0;
    while (i < sampleSize) {
        samples[i] = r.random.intRangeLessThan(i8, -128, 127);
        i = i+1;
    }
    return samples;
}

fn maxSubBrute(A: []const i8) [2]u32 {
    var i:u32 = 0;
    var j:u32 = undefined;
    var k:u32 = undefined;
    var range = []u32{0, 1};
    var max: i32 = @intCast(i32, A[1]) - @intCast(i32, A[0]);

    while(i < A.len-1){
        var diff: i32 = A[i];
        j = i+1;
        while(j < A.len){
            //try stdout.stream.print("A[{}] = {}\tA[{}] = {}\tmax = {}\n", i, A[i], j, A[j], max);
            diff = @intCast(i32, A[j]) - @intCast(i32, A[i]);
            if(diff > max){
                max = diff;
                range[0] = i;
                range[1] = j;
            }
            j = j+1;
        }
        i = i+1;
    }
    return range;
}

fn maxCrossingSub(A: []const i8) [3]i32 {
    var mid = A.len/2;
    var sub = []i32{@intCast(i32, mid), @intCast(i32, mid), @intCast(i32, A[mid])};

    var leftSum = @intCast(i32, A[mid]);
    var sum = leftSum;
    var i = mid-1;
    while(i > 0){
        sum += @intCast(i32, A[i]);
        if(sum > leftSum){
            leftSum = sum;
            sub[0] = @intCast(i32, i);
        }
        i = i-1;
    }

    var rightSum = @intCast(i32, A[mid]);
    sum = rightSum;
    i = mid+1;
    while(i < A.len){
        sum += @intCast(i32, A[i]);
        if(sum > rightSum){
            rightSum = sum;
            sub[1] = @intCast(i32, i);
        }
        i = i+1;
    }

    return sub;
}

fn maxSubArray(A:[]const i8) ![3]i32 {
    if(A.len == 1) return []i32{0, @intCast(i32, A.len-1), @intCast(i32, A[0])};

    var todo = try heap.alloc([2]usize, 1 + 2 * @intCast(usize, math.log2(A.len)));
    defer heap.free(todo);
    
    var i:usize = 0;
    var j:usize = 1;
    todo[0][0] = 0;
    todo[0][1] = A.len-1;

    while(i < j){
        const lo = todo[i][0];
        const hi = todo[i][1];

        if(lo < hi){
            const mid = @divFloor(lo + hi, 2);
            todo[j+0][0] = lo;
            todo[j+0][1] = mid;
            todo[j+1][0] = mid+1;
            todo[j+1][1] = hi;
            j = j + 2;
        }

        i = i + 1;
        try stdout.stream.print("i={} j={}\n", i, j);
    }

    // The last two should be a range of lo = hi.
    const range = todo[j-1];
    if(range[0] != range[1]) unreachable;
    var max = maxCrossingSub(A[range[0]..range[1]]);
    j = j - 2;

    while(true){
        const range2 = todo[j];
        const x = maxCrossingSub(A[range2[0]..range2[1]]);
        if(x[2] > max[2]) max = x;
        j = j - 1;
        if(j == 0) break;
    }

    return max;
}

pub fn printSamples(A: []const i8) !void {
    for (A) |s| {
        try stdout.stream.print("{}\t", s);
    }
    try stdout.stream.write("\n");
}

pub fn main() !void {
    stdout = FileOutStream.init(try std.io.getStdOut());
    const samples = try randomSample();

    try printSamples(samples[0..]);

    var range = maxSubBrute(samples[0..]);
    try stdout.stream.print("brute: {} to {}\n", range[0], range[1]);
    try stdout.stream.print("DONG!\n");

    // comment out these (2) lines and it compiles
    const sub = try maxSubArray(samples[0..]);
    try stdout.stream.print("max sub: {} to {} ({})\n", sub[0], sub[1], sub[2]);
}