蓝桥杯程序练习（2）

最大连续递增子序列（部分有序）：

问题描述：

在一组部分有序的数组中，找出长递增子序列。

例：（1， 9, 5，7, 3， 4， 6， 8， 0）中最长的递增子序列为（3， 4， 6，8）。

代码示例：

public class 最长连续递增子序列 {

	public static void main(String[] args) {
		int[] arr = {1, 9, 2, 5, 7, 3, 4, 6, 8, 9, 0};
		System.out.println("最大递增子序列的长度是：" + maxLenth(arr));
	}
	
	public static int maxLenth(int[] arr) {
		int maxLength = 0;
		int maxBegin = 0;
		int maxEnd = 0;
		int begin = 0;
		int end = 0;
		for(int i = 0; i < arr.length - 1; i++) {
			if(arr[i+1] >= arr[i]) {
				end++;
			}else {
				int length = end - begin + 1;
				if(length > maxLength) {
					maxBegin = begin;
					maxEnd = end;
					maxLength = length;
				}
				begin = end + 1;
				end++;
			}
		}
		System.out.print("最大递增的子序列是：");
		for(int i = maxBegin; i <= maxEnd; i++) {
			System.out.print(arr[i]);
		}
		System.out.println();
		return maxLength;
	}
}

程序运行结果：

最大递增的子序列是：34689
最大递增子序列的长度是：5

设计一个高效的求a的n次幂的算法：

public class a的n次幂 {
	public static void main(String[] args) {
		int n = 10;
		int a = 2;
		System.out.println(pow(a, n));
		System.out.println(pow1(a, n));
	}
	
	// 累乘法
	// 时间复杂度为 O(n)
	public static long pow(int a, int n) {
		long res = 1;
		for(int i = 0; i < n; i++) {
			res *= a;
		}
		return res;
	}
	
	/**
	 * 算法改进：
	 * 	通过减少累乘次数，提高算法的效率。
	 *      上面的方法需要累乘n次才可以得到结果。
	 *      下面改进后，例如：当求2^6的时候，按指数可以分解
	 *    指数 5 可以分为 2 * 2 + 2，即2^6 = (2^2)^2 * 2 * 2; 
	 *  即将原来的2*2*2*2*2*2简化为：((2*2)^2) * 2 * 2;
	 *  当指数很大时，可以极大减少累乘次数
	 * @param a
	 * @param n
	 * @return
	 */
	public static long pow1(int a, int n) {
		if(n ==  0) return 1;
		long res = a;
		int ex = 1;
		// 能翻
		while((ex<<1) <= n) {
			res *= res; // 翻
			ex<<=1;  // 指数
		}
		// 不能翻
		//差 n-ex次方没有乘到结果里面
		return res  * pow1(a, n - ex);
	}
}

程序运行结果：

1024
1024