DirectX3D 学习

学习DirectX3D

一组数中找最大的序列（综合）

int maxSumRect(int a[],int left,int right)
{
    if(left==right) //base case
        if(a[left]>0)
            return a[left];
        else
            return 0;
        
        int center = (left + right)/2;
        int maxLeftSum = maxSumRect(a, left, center);
        int maxRightSum = maxSumRect(a, center+1, right);
        
        int maxLeftBorderSum = 0, leftBorderSum = 0;
        
        for(int i = center; i >= left; i--)
            {
            leftBorderSum += a[i];
            if(leftBorderSum > maxLeftBorderSum)
                maxLeftBorderSum = leftBorderSum;
        }
        
        int maxRightBorderSum = 0, rightBorderSum = 0;
        for( i = center + 1; i<=right; i++)
        {
            rightBorderSum += a[i];
            if(rightBorderSum > maxRightBorderSum )
                maxRightBorderSum = rightBorderSum;
        }


        return max(maxLeftSum,max(maxRightSum,maxLeftBorderSum+maxRightBorderSum));
}


int maxSum2(int a[],int len)
{
    int maxSum = 0;
    int thisSum = 0;
    for(int i = 0; i < len; i++)
    {
        thisSum += a[i];
        if(thisSum > maxSum)
            maxSum = thisSum;
        else if( thisSum < 0)
            thisSum = 0;
    }
    return maxSum;

}
void MaxSubseq_DP(int nums[], int count, int &resStart, int &resEnd, int &resMax) 
{ 
    // 求数组nums[]中连续子序列的最大和，并标出该子序列 
    // 设 f[x] 为以 a[x] 终止且包含 a[x] 的最大序列的和，有： 
    // f[1] = a[1]; 
    // f[x+1] = f[x] > 0 ? f[x] + a[x+1] : a[x+1] 
    // 那么最大子序列的和就是 f[1] .. f[n] 中最大的一个 
    int start, max; 
    int i; 
    
    start = resStart = resEnd = 0; //初始化当前子序列和最大子序列为nums[0] 
    max = resMax = nums[0]; 
    
    for (i = 1; i < count; ++i) { 
        if (max > 0) { 
            max += nums[i]; 
        } else { 
            max = nums[i]; //抛弃当前子序列 
            start = i; //开始新的子序列搜索 
        } 
        
        if (resMax < max) { //更新最大子序列 
            resMax = max; 
            resStart = start; 
            resEnd = i; 
        } 
    }//for 
    
    return; 
}

posted on 2008-09-16 15:51 xpcer 阅读(1071) 评论(0)  编辑 收藏 引用 所属分类: C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2008年9月>
日一二三四五六
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

统计

常用链接

留言簿(1)

随笔分类

随笔档案

Graphics

搜索

最新评论

阅读排行榜

评论排行榜