大公司面试题 - 算法2

给一个整数数组A={a1,a2,…an}, 将这个数组首尾相接连成一个环状，它的一个子序列是指这个数组连续的一段，比如a2,a3…ak，或者an,a1…ai。请从这个环上选取两个不重叠的非空子序列，使这两个子序列中的所有数字之和最大。

例如: 1,-1,1,0 结果为2

1,-3,-1,2,-1 结果为2

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * <pre>
 * 给一个整数数组A={a1,a2,…an}, 将这个数组首尾相接连成一个环状，它的一个子序列是指这个数组连续的一段，比如a2,a3…ak，或者an,a1…ai。请从这个环上选取两个不重叠的非空子序列，使这两个子序列中的所有数字之和最大。
 * 例如:
 * 1,-1,1,0 结果为2
 * 1,-3,-1,2,-1 结果为2
 * </pre>
 *
 * @author chouy
 */
public class Interview2 extends Base
{
    private int maxSum = 0;

    public int getMaxSum()
    {
        return maxSum;
    }

    public void maxSubSequence(int[] array)
    {
        maxSum = array[0];
        debug(Arrays.toString(array));
        List<Integer> list = continousNumMerge(array);
        this.setMax(list);
        debug(list.toString());
        int loop = 1;
        while (list.size() >= 3)
        {
            int oldSize = list.size();
            debug("-------------- loop " + loop++ + " list.size=" + list.size() + " --------------");
            nearMerge(list);
            this.setMax(list);
            if (oldSize == list.size())
                break;
        }
        debug(list.toString());
    }

    /**
     * 合并相同符号的连续的数字
     *
     * @param array
     * @return
     */
    private LinkedList<Integer> continousNumMerge(int[] array)
    {
        LinkedList<Integer> list = new LinkedList<Integer>();
        boolean lastValueIsPlus = array[0] > 0;
        int v = array[0];
        for (int pos = 1; pos < array.length; pos++)
        {
            if (array[pos] > this.maxSum)
                this.maxSum = array[pos];
            if (array[pos] == 0)
                continue;
            if (lastValueIsPlus)
            {
                if (array[pos] > 0)
                {
                    v += array[pos];
                    continue;
                }
            }
            else
            {
                if (array[pos] < 0)
                {
                    v += array[pos];
                    continue;
                }
            }
            lastValueIsPlus = !lastValueIsPlus;
            list.add(v);
            v = array[pos];
        }
        list.add(v);
        // 如果得出数组首尾符号相同,则合并首尾

        if ((list.getFirst() > 0 && list.getLast() > 0) || list.getFirst() < 0 && list.getLast() < 0)
        {
            list.addFirst(list.removeFirst() + list.removeLast());
        }
        return list;
    }

    /**
     * 合并两个正数之间的负数小于这两个正数的和两个负数间的正数小于这两个负数
     */
    private void nearMerge(List<Integer> list)
    {
        for (int i = 1; i < list.size() - 1 && list.size() >= 3; i++)
        {
            Integer middle = list.get(i);
            // 正数

            if (middle > 0)
            {
                if (middle < -list.get(i - 1) && middle < -list.get(i + 1))
                {
                    merge3num(list, i);
                    i--;
                }
            }
            // 负数

            else
            {
                if (-middle < list.get(i - 1) && -middle < list.get(i + 1))
                {
                    merge3num(list, i);
                    i--;
                }
            }
        }
        /* 合并头尾 */
        // 合并头

        if (list.size() < 3)
            return;
        if (list.get(0) > 0)
        {
            if (list.get(0) <= -list.get(list.size() - 1) && list.get(0) <= -list.get(1))
            {
                int mergedValue = list.get(list.size() - 1) + list.get(0) + list.get(1);
                debug("merged pos: " + 0 + " value: " + list.get(list.size() - 1) + " " + list.get(0) + " "
                        + list.get(1) + " as " + mergedValue);
                list.remove(list.size() - 1);
                list.remove(1);
                list.remove(0);
                list.add(0, mergedValue);
                debug(list.toString());
            }
        }
        else
        {
            if (-list.get(0) <= list.get(list.size() - 1) && -list.get(0) <= list.get(1))
            {
                int mergedValue = list.get(list.size() - 1) + list.get(0) + list.get(1);
                debug("merged pos: " + 0 + " value: " + list.get(list.size() - 1) + " " + list.get(0) + " "
                        + list.get(1) + " as " + mergedValue);
                list.remove(list.size() - 1);
                list.remove(1);
                list.remove(0);
                list.add(0, mergedValue);
                debug(list.toString());
            }
        }
        // 合并尾

        if (list.size() < 3)
            return;
        if (list.get(list.size() - 1) > 0)
        {
            if (list.get(list.size() - 1) <= -list.get(list.size() - 2)
                    && list.get(list.size() - 1) <= -list.get(0))
            {
                int mergedValue = list.get(list.size() - 1) + list.get(0) + list.get(1);
                debug("merged pos: " + 0 + " value: " + list.get(list.size() - 2) + " "
                        + list.get(list.size() - 1) + " " + list.get(0) + " as " + mergedValue);
                list.remove(list.size() - 1);
                list.remove(list.size() - 1);
                list.remove(0);
                list.add(0, mergedValue);
                debug(list.toString());
            }
        }
        else
        {
            if (-list.get(list.size() - 1) <= list.get(list.size() - 2)
                    && -list.get(list.size() - 1) <= list.get(0))
            {
                int mergedValue = list.get(list.size() - 2) + list.get(0) + list.get(list.size() - 1);
                debug("merged pos: " + 0 + " value: " + list.get(list.size() - 2) + " "
                        + list.get(list.size() - 1) + " " + list.get(0) + " as " + mergedValue);
                list.remove(list.size() - 1);
                list.remove(list.size() - 1);
                list.remove(0);
                list.add(0, mergedValue);
                debug(list.toString());
            }
        }
    }

    /**
     * 把 List 中第 index 和它左右两个数相加后合并为一个数
     *
     * @param list
     * @param index
     */
    private void merge3num(List<Integer> list, int index)
    {
        int mergedValue = list.get(index - 1) + list.get(index) + list.get(index + 1);
        debug("merged pos: " + index + " value: " + list.get(index - 1) + " " + list.get(index) + " "
                + list.get(index + 1) + " as " + mergedValue);
        list.remove(index + 1);
        list.remove(index);
        list.remove(index - 1);
        list.add(index - 1, mergedValue);
        if (mergedValue > this.maxSum)
            this.maxSum = mergedValue;
        debug(list.toString());
    }

    private void setMax(List<Integer> list)
    {
        for (int i : list)
        {
            if (i > this.maxSum)
                this.maxSum = i;
        }
    }

    public static void main(String[] args)
    {
        Random random = new Random();
        int max = 10000;
        int[] is = new int[max];
        for (int i = 0; i < is.length; i++)
            is[i] = random.nextInt(max) - max / 2;
        Interview1 itv = new Interview1();
        itv.maxSubSequence(is);
        info("THE MAXSUM IS: " + itv.getMaxSum());
    }
}