LIS
LIS的优化说白了其实是贪心算法，比如说让你求一个最长上升子序列把，一起走一遍。
比如说（4, 2, 3, 1, 2，3，5）这个序列，求他的最长上升子序列，那么来看，如果求最长的上升序列，那么按照贪心，应该最可能的让该序列的元素整体变小，以便可以加入更多的元素。
现在开辟一个新的数组，arr[ 10 ]， { .......} --> 这个是他的空间 ，现在开始模拟贪心算法求解最长上升子序列，第一个数是4，先加进去，那么为{ 4 }再来看下一个数2，它比4小，所以如果他与4替换是不是可以让目前子序列（他这一个元素组成的子序列）变得更小，更方便以后元素的加入呢？是的。所以现在为{ 2 } 再来看他的下一个元素3，他要比2大，所以呢加在他的后面，{ 2, 3}
再看下一个元素是1，它比3要小，所以呢为了保证子序列整体尽可能的小（以便可以加入更多的元素），从目前的序列中查找出第一个比他大的数替换掉，那么就变成了{ 1， 3}，继续。。 下一个数是2，那么序列变为{ 1，2}，再下一个数为3，那么序列为{1，2，3}，在下一个数为5，那么序列为{1，2，3，5}，完。 目前序列里又4个元素，所以他的最长子序列的个数为4，但是这个序列是一个伪序列，里面的元素，并不是真正的最长上升子序列，而仅仅和最长上升子序列的个数一样。因为查找的时候用的二分查找，所以时间复杂度为o（nlogn）。
import java.util.*;
public class Main8 {
public static int findLongest(int[] s, int n) {
int []dp= new int[10001];
dp[0]=s[0];
int len=1;
for(int i=1;i<n;i++){
int left= 0,right=len-1,mid;
if(dp[len-1]<s[i])
dp[len++]=s[i]; //如果比最后一个大，直接把他放到最后一个
else{ //如果比最后一个元素小，那么就替换该序列第一个比他大的数
right=len-1;
while(left<=right){
mid= (left+right)/2;
if(dp[mid]<s[i])
left=mid+1;
else
right=mid-1;
}
dp[left]=s[i];
}
}
return len;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int[] A=new int[n];
for(int i=0; i<n; i++){
A[i]=sc.nextInt();
}
int res=findLongest(A, n);
// int res=n-max+1;
System.out.println(res);
}
}
}
最大大连续和
import java.util.*;
public class Main1 {
public static int getMax(int []num){
if(num==null||num.length==0)
return 0;
int edit=0;
int maxsum=Integer.MIN_VALUE;
for(int i=0;i<num.length;i++)
{
if(edit<0)
edit=0;
edit+=num[i];
maxsum=Math.max(edit, maxsum);
}
return maxsum;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int num[]=new int[n];
for(int i=0;i<n;i++)
num[i]=sc.nextInt();
int t=getMax(num);
System.out.println(t);
}
}
最大公共子串
蓝桥杯真题
#include <stdio.h>
#include <string.h> #define N 256
int f(const char* s1, const char* s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j; memset(a,,sizeof(int)*N*N);
int max = ;
for(i=; i<=len1; i++){
for(j=; j<=len2; j++){
if(s1[i-]==s2[j-]) {
a[i][j] =a[i-][j-]+; //填空
if(a[i][j] > max) max = a[i][j];
}
}
} return max;
} int main()
{
printf("%d\n", f("abcdkkk", "baabcdadabc"));
return ;
}