数据结构与算法分析 --几种常用的算法

package com.base.algorithmanalysis;

/**
 * 几种常见的算法
 * 
 * @author google
 * 
 */
public class Base {

	/**
	 * 针对排序后的序列折半查找策略： 最好的情况是需要查找的元素x是否为居中的元素，如果是，答案就找到了。
	 * 如果X小于居中元素，采用同样的策略应用于居中元素左边已经排好的子序列。 如果X大于居中元素，则检查右边的元素.
	 * 
	 * @param ary
	 * @param target
	 * @return
	 */
	public static int binarySearch(int[] ary, int target) {
		int low = 0, high = ary.length - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (ary[mid] < target) {
				low = mid + 1;
			} else if (ary[mid] > target) {
				high = mid - 1;
			} else {
				return mid;
			}
		}
		return -1;
	}

	/**
	 * 最大公因数的欧几得算法 计算机连续计算余数直到余数是0为止，最后的非0余数就是最大公因数
	 */
	public static long gcd(long m, long n) {
		while (n != 0) {
			long tem = m % n;
			m = n;
			n = tem;
		}
		return m;
	}

	/**
	 * 求幂操作
	 * 
	 * @param x
	 * @param n
	 * @return
	 */
	public static long pow(long x, int n) {
		if (n == 0)
			return 1;
		if (n == 1)
			return x;
		/**
		 * 此处递归说明(以x=4,n=2为例) 第一次进来:4%2==0 return pow(x*x,n/2) 【A】 则进入递归
		 * pow(16,1) ==> n==1,return 16. 向上返回 【A】 则有：4%2==0 return
		 * pow(x*x,n/2)=16;
		 */
		if (n % 2 == 0)
			return pow(x * x, n / 2);
		else
			return pow(x * x, n / 2) * x;
	}

	/**
	 * 求最大子序列和,数组总和中最大的和，
	 * 用一临时变量存储当前最大值，再拿数组每个累计与之比较，大的就交换，如果累计的值小，则不处理。
	 * @param a
	 * @return
	 */
	public static int maxSubSum(int[] a) {
		int maxSum = 0, thisSum = 0;
		for (int j = 0; j < a.length; j++) {
			thisSum += a[j];
			if (thisSum > maxSum)
				maxSum = thisSum;
			else if (thisSum < 0)
				thisSum = 0;
		}
		return maxSum;
	}

	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		 int[] aIs = { 10,10,10,20,-30,-49,1};
		// System.out.println("找到10,在索引" + binarySearch(aIs, 10) + "处");
		// System.out.println("15和55的最大公因数是：" + gcd(15, 50));
//		System.out.println(pow(4, 2));
		//最大子序列之和计算
		System.out.println(maxSubSum(aIs));
	}
}