воскресенье, 20 марта 2011 г.

Наибольшая общая подпоследовательность


public class SequenceTest {
                      //0  1   2  3   4  5  6  7   8
    static int[] qwe = {1, 4, -6, 2, -1, 5, 2, 0, -6};
    //static int[] qwe = {1, 2, 3, 4, 5, 6, 7};

    @Test
    public void test() {

        int maxSum = 0;
        int i1 = 0;
        int i2 = 0;

        int newSum = 0;
        int i1n = 0;
        int i2n = 0;

        for (int i = 0; i < qwe.length; i++) {
            int x = qwe[i];
            if (newSum == 0) {
                i1n = i;
            }
            i2n = i;

            int current = newSum + x;
            if (current > newSum) {//подпоследовательность растёт
                newSum = current;
            } else {//подпоследовательность начала уменьшаться

                if (newSum > maxSum) {//если сумма текущей подпоследовательности больше чем maxSum - запомним её
                    maxSum = newSum;
                    i1 = i1n;
                    i2 = i2n;
                }
                if (current <= 0) {//если подпоследовательность меньше 0 она уже не может быть полезной
                    newSum = 0;
                    i1n = 0;
                    i2n = 0;
                } else {//продолжаем рассматривать уменьшающуюся последовательность
                    newSum = current;
                }
            }
        }

        if (maxSum == 0 && newSum > 0) {
            maxSum = newSum;
            i1 = i1n;
            i2 = i2n;
        }

        System.out.println(i1 + "-" + i2 + "  maxSum:" + maxSum);
    }
}


Комментариев нет:

Отправить комментарий