最大子序列和,动态规划.txt

里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等

#include <iostream>
using namespace std ;

void MaxSubSum(int nums[], int count, int &resStart, int &resEnd, int &resMax)
{
    
    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;
        }
    }
    return;
}
int main()
{
	int begin,end,max;
    int a[]={4,-4,1,2};
    MaxSubSum(a,4,begin,end,max);
	cout << "原来序列为: " ;
	for( int j = 0 ; j < 4 ; j ++)
		cout << a[j] << " " ;
	cout << endl ;
    cout << "最大和为:" << max << endl;
    cout << "和最大序列为: " ;
    for(int i = begin ; i <= end ;i ++)
	   cout << a[i] << " " ;
    cout << endl ;
    return 1;
}