学步园

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.

最大子段和，很常见的了。

一个简单的DP思想，dp[i] = max{ dp[i-1]+A[i] , A[i] } ,最后找最大的dp[i] 就是了，因为每次只用到dp[i-1]，所以可以用一个pre变量来代表它，然后就成O(1)的空间了。

最大连续和还有很多种变形，比如限定长度，比如允许环形等等，其实基本思路就是：

我们先求一个递增和数组： Sum[i] = Sum[i-1] + A[i] ，那么最大字数组和就是找这个数组中差最大的两个位置的差值而已，条件是必须两个数必须大的在右边而已。

所以从这个本质出发，所有的变形就很好转化为已经掌握了的其他同等问题了。

比如限定长度的，就成了每个数求它左边K个数这个范围内与自己最大的差值，这个很明显用单调队列优化下就是了。

先上这个题的代码吧。

class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        assert(A&&n>=0);
	    if ( n==0 )
		    return 0;
	    int pre=A[0];
	    int maxSum=A[0];
	    for(int i=1;i<n;i++)
	    {
		    pre=max(A[i],pre+A[i]);
		    maxSum=max(maxSum,pre);
	    }
	    return maxSum;
    }
};

上面DP的算法是O(N)的，题目中还提示我们再尝试用分治法来做一下。

分治法，大家会想到求出左边最大跟右边最大，然后求一下中间连接的，三者比较然后返回最大，可是求中间连接最大的时候是O(n)的，所以导致最后的算法是O(nlogn)的，明显不是最优的。

下面是我写的一个分治法，因为是在O(1)的时间求出中间连接最大，所以算法是O(logN)的，可以看出比DP效率还要好一些。

算法应该比较好理解了，就不多费口舌了。其中left,right 分别表示该区间从左起的最大值，从右起的最大值。

至于更新的策略大家找个例子想一想就能想通了。

class Solution {
public:
    int maxSubArray(int A[], int n) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function

		assert(A&&n>=0);
		if ( n==0 )
			return 0;
		vector<int> num(A,A+n);
		vector<int> sum(n,0);
		sum[0]=num[0];
		for(int i=1;i<n;i++)
			sum[i]=sum[i-1]+A[i];
		int left,right,maxSum;
		solve(sum,num,0,n-1,left,right,maxSum);
		return maxSum;
	}
	void solve(vector<int>& sum,vector<int>& num,int l,int r,int& left,int& right,int& maxSum)
	{
		if ( l==r )
		{
			left=right=maxSum=num[l];
			return;
		}
		int mid=(l+r)>>1;
		int lLeft,lRight,lMax;
		solve(sum,num,l,mid,lLeft,lRight,lMax);
		int rLeft,rRight,rMax;
		solve(sum,num,mid+1,r,rLeft,rRight,rMax);
		maxSum=max(lMax,max(rMax,lRight+rLeft));

		int leftSum = sum[mid]-sum[l]+num[l] ;
		left=max(lLeft,leftSum+rLeft);
		int rightSum= sum[r]-sum[mid];
		right=max(rRight,rightSum+lRight);
	}
};

Edit Distance：

Given two words word1 and word2,
find the minimum number of steps required to convert word1 to word2.
(each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character

b) Delete a character

c) Replace a character

class Solution {
public:
    int minDistance(string word1, string word2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int l1=word1.length();
	    int l2=word2.length();
	    
	    vector<vector<int> > dp(l1+1,vector<int>(l2+1,0));
	    dp[0][0]=0;
	    for(int i=1;i<l1+1;i++)
		    dp[i][0]=i;
	    for(int j=1;j<l2+1;j++)
		    dp[0][j]=j;
	    for(int i=1;i<=l1;i++)
	    {
		    for(int j=1;j<=l2;j++)
		    {
			    if(word1[i-1]==word2[j-1] )
				    dp[i][j]=dp[i-1][j-1];
			    else 
			    {
				    dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
			    }
		    }
	    }
	    return dp[l1][l2];
    }
};