大公司面试算法题 - 第二题

昨天发了第一题，今天发第二题。这个题目在一个网络竞赛中有，当时因为时间没做出来，没想到面试又遇到了。

看来平时对问题的深入钻研还是非常有用的。我当时要在赛后再好好钻研一下，没准就面试通过了。

下面看题目：




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

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

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


下面是解题代码，Base类的代码在上一篇博客中可以找到：


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());
    }
}