最大子序列和,蛮力法.txt

来自「里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等」· 文本 代码 · 共 43 行

#include <iostream>
using namespace std ;

void MaxSubSum(int a[] ,int n, int& first ,int& last, int& max) 
{
	int i,j ; 
	int b[20][20] ;
	for(i = 0  ; i < n ; i ++) b[i][i] = a[i] ;
	for( i =  0; i < n ;i ++ )
		for(int j = i+1 ; j < n ;j ++)
			b[i][j] = b[i][j-1] + a[j] ;
	max = b[0][0] ;
	for(i = 0 ;i < n ; i ++)
		for(j = 0 ; j < n ;j ++)
			if(b[i][j] > max ) 
			{
				max = b[i][j] ;
				first = i ;
				last = j ;
			}
}
	

int main()
{
	int n ,i ,j ,max ,first, last ;//first ,last
	int *a ;
	cin >> n ;
	a = new int[n] ;
	for( i =  0 ;i  < n ; i ++)
		cin >> a[i] ;
	MaxSubSum(a,n,first, last,max);
	cout << "原来序列为: " ;
	for( j = 0 ; j < n ; j ++)
		cout << a[j] << " " ;
	cout << endl ;
    cout << "最大和为:" << max << endl;
    cout << "和最大序列为: " ;
    for( i = first; i <= last ;i ++)
	   cout << a[i] << " " ;
    cout << endl ;
    return 1;
}