2019-03-05

每天一道算法题

题目:炎热的夏日，KC非常的不爽。他宁可忍受北极的寒冷，也不愿忍受厦门的夏天。最近，他开始研究天气的变化。他希望用研究的结果预测未来的天气。经历千辛万苦，他收集了连续N（1<=N<=10^7）天的最高气温数据。

现在，他想知道最高气温一直上升的最长连续天数。
输入输出格式
输入格式：
*1行：一个整数N。1<=N<=10^7
*2行：N个空格隔开的整数，表示连续N天的最高气温。0<=最高气温<=10^9。

输入样例#1：

10
1 2 3 2 4 5 6 8 5 9
输出样例#1：
5
分析:
如下面代码，求最长上升子序列，需要用sum来计算每一次序列长度，然后s来存储最大上升子序列的长度。

public class LIS {
    //求数组arr的最大上升子序列长度
    public static int LongestLength(int[] arr) {
        int N = arr.length;
        int[] seqLen  = new int[N];
        //seqLen每个字符前的最大上升子序列长度，初始化为1
        for(int i = 0;i< N; i++)
            seqLen[i] = 1;
        
        for(int i = 1;i< N; i++) {
            for(int j = 0;j < i; j++) {
                if(arr[j] < arr[i] && seqLen[j]+1 >seqLen[i])
                    seqLen[i] = seqLen[j] + 1;
            }
        }
        int maxlen = 0;
        int index = 0;
        for(int i = 1;i< N; i++) {
            if(seqLen[i]>maxlen) {
                maxlen = seqLen[i];
                index = i;
            }
        }
            
        System.out.println(index);
        System.out.println(maxlen);
        
        return maxlen;
        
    }

方法二

import java.util.Scanner;
public class Main{
  public static void main (String[]args)
{
       Scanner sc=new Scanner(System.in);
       int b=0,count=0;sum=-1,temp=0 ,a=sc.nextInt();
        for(int i=0;i<a;i++)
           {
                count=sc.nextInt();
                  if (count>sum)
                {  temp++;
                    }else{
                  if(sum>count)
                    {  b=temp;
                    }
                     sum=count;
                   }
            System.out.print(b);
}
}