계산수 그룹의 가장 큰 하위 그룹의 합(인수)

1349 단어 algorithms
이 문제를 보면 이것이 전형적인 동적 기획 문제라는 것을 알 수 있다. 코드는 다음과 같다.
/*************************************************************
 * file:calmax_child_array_sum.c
 * brief:  DP,            ,        
	         O(n^2)
	         O(n),               
 * [email protected]    1.0      creat
 *************************************************************/
 #include 
 #include 

void dp_calmax_child_array_sum(int array[], int n, int* start_index, int* end_index, int* max_sum){
	if(!array || !n)
		return;
	int tmp_max = 0;
	int i = 0;
	while(i < n){
		//        0,    ,      
		if(tmp_max <= 0){
			*start_index = i;
			tmp_max = array[i];
		}
		else
			tmp_max += array[i];
			
		//      ,     ,      
		if(tmp_max > *max_sum){
			*max_sum = tmp_max;
			*end_index = i;
		}
		++i;
	}
	return;
}

int main(int argc, char* argv[]){
	int array[] = {1, -2, 3, -4, 6, 7, -10, 4, 5, 6, -1};
	int start_index, end_index, max_sum;
	dp_calmax_child_array_sum(array, sizeof(array)/sizeof(int), &start_index, &end_index, &max_sum);
	
	printf("start_index:%d, end_index:%d, max_sum:%d 
", start_index, end_index, max_sum); return 1; }

하지만 상기 코드가 충분한 테스트를 거치면 문제가 있을 것입니다.
예를 들어 모두 마이너스인 그룹을 처리할 수 없기 때문에 (실제로는 가장 큰 마이너스를 찾아야 한다) 당분간 좋은 방법을 생각하지 못하고 먼저 붙여서 집에 가서 업데이트를 한다.

좋은 웹페이지 즐겨찾기