学步园

package arithmetic;

import java.util.Arrays;

public class SumOfSubSequence {
	/*
	 * 求组数的最大子串和(连续)
	 */
	public static int maxSum(int data[], int n) {
		int sum, max;
		sum = max = data[0];
		for (int i = 0; i < n; i++) {
			if (sum < 0)
				sum = data[i];
			else
				sum += data[i];
			if (sum > max)
				max = sum;
		}
		return max;
	}

	/*
	 * 求最长公共子串(连续);只返回长度，不返回匹配的序列
	 */
	public static int[] getMatchNum(int a[], int b[])// 只返回长度，不返回子序列
	{
		int max = 0, c[] = new int[b.length];// 用一个数组就可以表示它的左上角的数是多少
		int pos = 0;
		for (int i = 0; i < a.length; i++) {
			for (int j = b.length-1; j >=0; j--) { //这里为什么是要从后向前比较？和那个用一维数组求0-1背包一样，都要从后向前比较
				if (a[i] == b[j] && j == 0)
					c[j] = 1;
				else if (a[i] == b[j])
					c[j] = c[j - 1] + 1;
				else
					c[j] = 0;
				if (c[j] > max) {
					max = c[j]; // 记录最多匹配连续的个数
					pos = j;
				}
			}
			//System.out.println(Arrays.toString(c));
		}
		int result[] = new int[max];
		for (int i = pos - max + 1; i <= pos; i++)
			result[i - pos + max - 1] = b[i];
		return result;
	}
	/*
	 * 	重载上面的方法
	 * */
	public static String getMatch(String a,String b)
	{
		int c[] = new int[b.length()];
		StringBuffer result = new StringBuffer();
		int max = 0,pos = 0;
		for(int i=0;i<a.length();i++)
			for(int j=b.length()-1;j>=0;j--)
			{
				if(a.charAt(i)==b.charAt(j)&& j==0)
					c[j] = 1;
				else if(a.charAt(i)==b.charAt(j))
					c[j]=c[j-1]+1;
				else
					c[j] = 0;
				if(max<c[j])
				{
					max = c[j];
					pos = j;
				}
			}
		for(int i=pos-max+1;i<=pos;i++)
			result.append(b.charAt(i));
		return result.toString();
	}
	/*
	 * 	最长公共子序列（不连续）
	 * 	公式：c[i][j] = |-	0 (i=0||j=0)
	 * 					|-	c[i-1]c[j-1]	(a[i]==b[j])
	 * 					|-	max(c[i][j-1],c[i-1][j])
	 * */
	public static int[][] getPath(String a,String b)
	{
		int c [][] = new int[a.length()+1][b.length()+1];
		int path[][] = new int[a.length()+1][b.length()+1]; //定义路线    左上角：0 左边：－1 上边：1
		//  因为都是从1 下标开始，对String 进行处理
		a = "_"+a;
		b = "_"+b;
		for(int i=1;i<a.length();i++)
			for(int j=1;j<b.length();j++)
			{
				if(a.charAt(i)==b.charAt(j))
				{
					c[i][j] = c[i-1][j-1]+1;
					path[i][j] = 1;
				}
				else
					if(c[i-1][j]>=c[i][j-1])// 上边>左边
					{
						c[i][j] = c[i-1][j];// 上边
						path[i][j] = 2;
					}
					else
					{
						c[i][j] = c[i][j-1];
						path[i][j] = 3;// 左边
					}
				
			}
		return path;
	}
	public static void getCloseMath(int i,int j,String a,int[][] path)
	{
		if(i==0||j==0)
			return;
		if(path[i][j]==1)
		{
			getCloseMath(i-1,j-1,a,path);
			System.out.print(a.charAt(i-1));
		}
		else
			if(path[i][j]==2)
			getCloseMath(i-1,j,a,path);
			else
				getCloseMath(i,j-1,a,path);
	}
	public static void main(String args[]) {
		
		int a[] = {0,1, 2, 3, 4, 0, 5, 6, 7, 8 };// 作为行
		int b[] = {0,1, 2, 3, 4, 9, 5, 6, 7, 8 };// 作为例
		System.out.println(Arrays.toString(getMatchNum(a, b)));
		String as = "123";
		String bs = "43678";
		System.out.println(getMatch(as,bs));
		String rs = "ABCBDAB";
		String cs = "BDCABA";
		int c[][] = getPath(rs,cs);
		getCloseMath(c.length-1,c[0].length-1,rs,c);
	}
}