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 操作。
