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

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

XStream vs Simple

XStream  быстрее чем Simple приблизительно в два раза. Тестил под Windows. Для теста были созданы сущности с дублирующими друг друга аннотациями для XStream и Simple.




Класс тестика:

package ru.test.serialization;



import com.thoughtworks.xstream.XStream;
import com.thoughtworks.xstream.io.xml.*;
import org.junit.Test;
import org.simpleframework.xml.convert.AnnotationStrategy;
import org.simpleframework.xml.core.Persister;
import org.simpleframework.xml.strategy.Strategy;
import java.io.StringWriter;
/**
 * @author k.burmistrov
 */
public class SimpleVSXstream {
        @Test public void test() {
        XStream xStream = new XStream(new DomDriver());
        Persister serializer = new Persister();
        long smplstart;
        long smplexecTime = 0;
        Container container;
        long xsstart;

        long xsexecTime = 0;
        String res = "";

        for (int i = 0; i < 100; i++) {
            container = ContainerCreator.getContainer();
            xsstart = System.currentTimeMillis();
            res = xStream.toXML(container);
            xsexecTime = xsexecTime + (System.currentTimeMillis() - xsstart);
            StringWriter writer = new StringWriter();

            try {

                smplstart = System.currentTimeMillis();
                serializer.write(container,writer);
            } catch (Exception e) {
                smplstart = System.currentTimeMillis();
                e.printStackTrace();
            }
            res = writer.toString();
            smplexecTime = smplexecTime + (System.currentTimeMillis() - smplstart);
        }

        System.out.println( "XSTREAM x 100 = " + xsexecTime);

        System.out.println( "SIMPLE x 100 = " + smplexecTime);

        System.out.println("\n" + ContainerCreator.toDebugString(res));
    }
}

Результирующий вывод:
XSTREAM x 100 = 138 SIMPLE x 100 = 213




<CONTAINER PART="0">
   <BIG CODE="String code 50.35868861427403564" LOGIN="String login 50.7245088483040268" SUBADDRESS="0">
      <PART PART="0" SERIAL="0"/>
      <BIG CODE="String code" LOGIN="String login" SUBADDRESS="0">
         <PART PART="0" SERIAL="0"/>
      </BIG>
      <BIG CODE="String code 10.06973240045944129" LOGIN="String login 10.9788960825360289" SUBADDRESS="0">
         <PART PART="0" SERIAL="0"/>
      </BIG>
      <BIG CODE="String code 20.627970543681521" LOGIN="String login 20.5815827829176397" SUBADDRESS="0">
         <PART PART="0" SERIAL="0"/>
      </BIG>
      <BIG CODE="String code 30.9800044849451679" LOGIN="String login 30.5987182743788726" SUBADDRESS="0">
         <PART PART="0" SERIAL="0"/>
      </BIG>
      <BIG CODE="String code 40.9685538564759587" LOGIN="String login 40.11954755881153056" SUBADDRESS="0">
         <PART PART="0" SERIAL="0"/>
      </BIG>
   </BIG>
   <BIG CODE="String code 60.9978869534936364" LOGIN="String login 60.22744058846132909" SUBADDRESS="0">
      <PART PART="0" SERIAL="0"/>
      <BIG CODE="String code" LOGIN="String login" SUBADDRESS="0">
         <PART PART="0" SERIAL="0"/>
      </BIG>
      <BIG CODE="String code 10.06973240045944129" LOGIN="String login 10.9788960825360289" SUBADDRESS="0">
         <PART PART="0" SERIAL="0"/>
      </BIG>
      <BIG CODE="String code 20.627970543681521" LOGIN="String login 20.5815827829176397" SUBADDRESS="0">
         <PART PART="0" SERIAL="0"/>
      </BIG>
      <BIG CODE="String code 30.9800044849451679" LOGIN="String login 30.5987182743788726" SUBADDRESS="0">
         <PART PART="0" SERIAL="0"/>
      </BIG>
      <BIG CODE="String code 40.9685538564759587" LOGIN="String login 40.11954755881153056" SUBADDRESS="0">
         <PART PART="0" SERIAL="0"/>
      </BIG>
   </BIG>
</CONTAINER>

PS: значение атрибутов генериловалось для каждой итерации новое