1. 实验环境

操作系统:Mac 64
运行内存:16GB
编程语言:Java
编译环境:Eclipse

2. 题目要求

设计一个Ο(nlgn)时间的算法，求一个 n 个数的序列的最长单调递增子序列。

A. 用户界面输入原始序列

设计便于用户操作的界面，可以输入 n 个数，在计算后输出最长单调递增子 序列和该子序列的长度。

B. 求最长单调递增子序列

获取文本框内容，依次遍历字符串的单个字符，如果递增，直接加入。否则， 采用二分法缩小递归范围，如果递增，需要修改值，而非加入。该算法时间复杂 度 Ο(nlgn)。

C. 用户界面得到子序列及长度

将求得的子序列及该子序列的长度返回到用户界面的文本框中。

D. 用户界面重置和计算

点击计算可求出子序列和长度。点击重置可重新输入序列并求结果。

4.项目结构

程序结构如下图所示，lmis_str.java 可处理多长度的序列;而 lmis_list_num.java 只可处理 int/long 范围的序列。项目结构如下图所示。

5. 实验结果

A. 程序运行界面和正确性

程序编译运行结果如下图所示。

图 1 程序编译运行结果界面 程序输入序列，运行结果如下图所示。

图 2 程序运行结果界面

6.实验代码

实现用户界面 求单调最长递增子序列

package dp;

import java.awt.EventQueue;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextField;
public class lmis_str extends JFrame{
    public static ArrayList<Integer> list=new ArrayList<Integer>();
    public JPanel mainPanel=new JPanel();
    public JLabel jLabel=new JLabel("输入序列:");
    public JTextField jTextField=new JTextField(40);
    public JLabel jLabel1=new JLabel("递增子序列:");
    public JTextField jTextField1=new JTextField(40);
    public JLabel jLabel2=new JLabel("递增子序列长度:");
    public JTextField jTextField2=new JTextField(40);
    public JButton rebtn=new JButton("重置");
    public JButton calbtn=new JButton("计算");
    public static void main(String[] args) {
        EventQueue.invokeLater(new Runnable() {
            public void run() {
                try {
                    //继承JFrame
                    lmis_str frame = new lmis_str();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        });
    }
    public lmis_str(){
        
        mainPanel.add(jLabel);
        mainPanel.add(jTextField);
        mainPanel.add(jLabel1);
        mainPanel.add(jTextField1);
        mainPanel.add(jLabel2);
        mainPanel.add(jTextField2);
        mainPanel.add(rebtn);
        mainPanel.add(calbtn);
        this.add(mainPanel);
        this.setTitle("计算最长递增子序列:");
        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        this.setVisible(true);
        this.setBounds(0, 0, 600, 600);
        calbtn.addActionListener(new ActionListener() {
            
            @Override
            public void actionPerformed(ActionEvent e) {
                String string=jTextField.getText();
                jTextField1.setText(getLmis(string));
                jTextField2.setText(String.valueOf(getLmis(string).length()));
                
                
            }
        });
        rebtn.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(ActionEvent e) {
                jTextField.setText("");
                jTextField1.setText("");
                jTextField2.setText("");
            }
        });
        
    }
    public String getLmis(String str){
        List<Character> list=new ArrayList<Character>();
        list.add(str.charAt(0));
        int index=0;
        for(int i=0;i<str.length();i++){
            char c=(char) (str.charAt(i)-'0');
            if(list.get(index)<c){
                list.add(++index,c);
            }else{
                int low=0;
                int high=index;
                while (low<high) {
                    int middle = (low+high)>>1;
                      if(list.get(middle)<c)
                        low=middle+1;
                    else {
                        high=middle-1;
                    }
                }
                if(list.get(low)<c&&(low+1)<list.size())
                    list.set(low+1, c);
                else
                    list.set(low, c);
            }
        }
        System.out.println(list.size());
        StringBuffer sBuffer=new StringBuffer();
        for(int t:list){
            sBuffer.append(t);
        }
        return new String(sBuffer);
    }
}

7. 实验技巧与注意点

A. 在处理 n 个数时，可直接处理 string 的单个字符，这样不会限制长度。如果 处理 int/long 时会有位数的限制。
B. 在存储原始序列和结果子序列时，应使用 list，这样可以动态增加字符。如 果使用 Array，结果长度并不确定。
C.向 list 添加值时，需要将数字向字符转换，做(字符-‘0’)的操作。
D. 动态规划过程中，只有递归到最长子序列递增时才需要add，递归到递增需 要做 set 操作。