首页 > 代码库 > 增序子数组个数

增序子数组个数

2024-11-01 18:58:39   209人阅读

问题描述：

　　　　微软10.15笔试：对于一个数组{1,2,3}它的子数组有{1,2}，{1,3}{2,3}，{1,2,3}，元素之间可以不是连续的，对于数组{5,9,1,7,2,6,3,8,10,4}，

        升序子序列有多少个？或者换一种表达为：数组int a[]={5,9,1,7,2,6,3,8,10,4}  。求其所有递增子数组(元素相对位置不变)的个数，  

        例如：{5，9}，{5，7，8，10}，{1，2，6，8}。

 

思想： 动态规划

 

代码： 

 1 import java.util.Scanner; 2  3  4 public class Main { 5  6     public static void main(String[] argv){ 7          8         Scanner in = new Scanner(System.in);         9         String [] k = in.nextLine().split(" ");        10         int [] s = new int[k.length];11         int [] id = new int[k.length];12         int [] out = new int[k.length];13         int sum=0;14         //System.out.println(k.length);15         for (int i=0; i<k.length; i++){16             s[i]=Integer.parseInt(k[i]);17             out[i]=0;18         }19         in.close();20         /* 每个值在数组中的大小序号 */21         for(int i=0; i<s.length; i++){22             int n=0;23             for(int j=0; j<s.length; j++){24                 if(s[i]>s[j])25                     n++;26             }27             id[i]=n;            28         }29         //System.out.println(" "+id[0]+id[1]+id[2]+id[3]);30         31         /* 动态规划 */32         for(int i=0; i<id.length; i++){33             34             out[id[i]]=out[id[i]]+1;35             for(int j=0; j<id[i]; j++){36                 out[id[i]]=out[id[i]]+out[j];37             }38             //System.out.println(" "+id[i]+": "+out[id[i]]);39             sum=sum+out[id[i]];40         }41         42         /* 输出结果 */43         System.out.println(sum);44         45     }46     47 }

 

增序子数组个数


联系
我们