LeetCode的medium题集合(C++实现)八

1 Pow(x, n) 该题采用二分法进行递归

double myPow(double x, int n) {if(n==0) return 1;if(n<0){n=(-n);x=1/x;}double res=myPow(x,n/2);if(n%2==0){return res*res;}else{return res*res*x;}}

2 Maximum Subarray Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [2,1,3,4,1,2,1,5,4], the contiguous subarray [4,1,2,1] has the largest sum = 6. 该题可以采用动态规划解决，. 很显然，当当前的最大值小于0时，，计算下一个值时将小于0的数丢弃。

int maxSubArray(vector<int>& nums) {int max=INT_MIN;int n=nums.size();int mid=0;for(int i=0;i<n;i++){//这里用mid,max替代dp数组以节省空间mid=mid+nums[i];mid=(nums[i]>=mid?nums[i]:mid);if(mid>max){max=mid;}}return max;}

要么读书、要么旅行，灵魂和身体，必须有一个在路上。