分治-最大子段和

最近心血来潮想写点算法、数据结构的代码，所以就又拿出《算法导论》温习了一遍分治算法。
本来以为自己对分治算法已经了解的很深了，但是重新看一遍才发现，实现分治算法并不难，难点在于对实际问题向分治算法的转变。书中给出的问题是找出连续N天股票买入卖出能获得的最大收益，这个问题用了相对值的角度一变形就成为了一个能够用分治策略解决的问题。所谓人才和平庸的差距，可能就在这个转化里面吧。
分治算法就是把一个大问题拆分成N个相同类型的小问题(即小规模的问题)，然后通过解决每个小问题来求解大问题：

对于每个问题，都有T(N)=2T(N/2)，其中T代表解决问题的时间代价。对它求解可得T(N)=O(NlgN)。

最大子段和

问题描述

对于一个数组a，求它的子数组中和最大的子数组。
这里隐含了a中含负数，否则最大子数组就是它本身了。

问题拆分

对于最终解，无外乎一下3种情况：

1. 解存在于a[head…mid];
2. 解存在于a(mid…tail];
3. 解跨过中间的值a[head…mid…tail];

设
findMax(long[] a, int left, int right)为1、2情况下的解，
findCross(long[] a, int left, int mid, int right)为3情况下的解;
那么只需找出
findMax(a, head, mid)、findMax(a, mid+1, tail)、findCross(a, head, mid, tail)
这3者当中的最大值即可。

hdu1003
AC code

import java.io.*;

/**
 * @author hero
 */
public class Main implements Runnable {

    public void solve() {
        int total = nextInt();
        for (int i = 1; i <= total; i++) {
            int len = nextInt();
            long[] a = new long[len];
            for (int j = 0; j < len; j++) {
                a[j] = nextLong();
            }
            Result result = findMax(a, 0, a.length - 1);
            out.println("Case " + i + ":");
            out.println(result.sum + " " + (result.left + 1) + " " + (result.right + 1));
            if (i != total) {
                out.println();
            }
        }
    }

    @Override
    public void run() {
        init();
        solve();
        out.flush();
    }

    public static void main(String[] args) {
        new Main().run();
    }

    StreamTokenizer in;
    PrintWriter out;

    public void init() {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
    }

    public int nextInt() {
        try {
            in.nextToken();
            return (int) in.nval;
        } catch (IOException e) {
            throw new IllegalStateException(e);
        }
    }

    public long nextLong() {
        try {
            in.nextToken();
            return (long) in.nval;
        } catch (IOException e) {
            throw new IllegalStateException(e);
        }
    }

    public Result findMax(long[] a, int left, int right) {
        if (left == right) {
            return new Result(left, right, a[left]);
        } else {
            int mid = (left + right) >> 1;
            Result ls = findMax(a, left, mid);
            Result rs = findMax(a, mid + 1, right);
            Result cs = findCross(a, left, mid, right);
            return max(ls, max(rs, cs));
        }
    }

    private Result findCross(long[] a, int left, int mid, int right) {
        long leftMax = Integer.MIN_VALUE;
        long leftSum = 0;
        int idxL = mid;
        for (int i = mid; i >= left; i--) {
            leftSum = leftSum + a[i];
            if (leftSum >= leftMax) {
                leftMax = leftSum;
                idxL = i;
            }
        }
        long rightMax = Integer.MIN_VALUE;
        long rightSum = 0;
        int idxR = mid + 1;
        for (int i = mid + 1; i <= right; i++) {
            rightSum = rightSum + a[i];
            if (rightSum > rightMax) {
                rightMax = rightSum;
                idxR = i;
            }
        }
        return new Result(idxL, idxR, leftMax + rightMax);
    }

    class Result implements Comparable<Result> {
        public int left;
        public int right;
        public long sum;

        public Result(int left, int right, long sum) {
            this.left = left;
            this.right = right;
            this.sum = sum;
        }

        @Override
        public int compareTo(Result o) {
            return (int) (this.sum - o.sum);
        }

        @Override
        public String toString() {
            return "Result{" +
                    "left=" + left +
                    ", right=" + right +
                    ", sum=" + sum +
                    '}';
        }
    }

    private Result max(Result a, Result b) {
        return a.compareTo(b) > 0 ? a : b;
    }
}