算法设计与应用基础作业第二周

53. Maximum Subarray          

Descripyion：

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.

class Solution {public:    static int MaxSubSequence(vector <int>& A ,int N)    {    	return MaxSubSum(A,0,N-1);    }    static int Max(int a, int b, int c)    {    	return max(a, max(b,c));    }    static int MaxSubSum(vector <int>& A , int Left, int Right)    {    	int MaxLeftSum,MaxRightSum;    	int MaxLeftBorderSum,MaxRightBorderSum;    	int LeftBorderSum,RightBorderSum;    	int Center,i;	    	if(Left == Right)    	{	    	return A[Left];    	}	    	Center = (Left + Right)/2;    	MaxLeftSum = MaxSubSum(A,Left,Center);    	MaxRightSum = MaxSubSum(A,Center+1,Right);	    	MaxLeftBorderSum = A[Center];    	LeftBorderSum = 0 ;    	for(i = Center ;i >= Left;i--)    	{	    	LeftBorderSum += A[i];    		if(LeftBorderSum > MaxLeftBorderSum)    			MaxLeftBorderSum = LeftBorderSum;    	}	    	MaxRightBorderSum = A[Center + 1];    	RightBorderSum = 0 ;    	for(i = Center+1;i <= Right;i++)    	{	    	RightBorderSum += A[i];	    	if(RightBorderSum > MaxRightBorderSum)	    		MaxRightBorderSum = RightBorderSum;    	}		    	    return Max(MaxLeftSum,MaxRightSum,MaxLeftBorderSum + MaxRightBorderSum);	         }         int maxSubArray(vector<int>& nums) {        int n = nums.size() ;        return MaxSubSequence(nums , n) ;    }};
171. Excel Sheet Column Number          
Description:
Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:
    A -> 1    B -> 2    C -> 3    ...    Z -> 26    AA -> 27    AB -> 28 
分析：这道题可以类比十进制数字的表示来做，例如：
     121 = 1*10^2+2*10^1+1*10^0 
     因此，就可以轻易地写出如下代码：
My C++ code:
class Solution {public:    int titleToNumber(string s) {        int total = 0 ;        int i = s.length() ;        for ( ; i > 0 ; i --)        {            total += (s[ i - 1 ] - 'A' + 1) * pow(26 , s.length() - i) ;        }        return total ;    }};