계산수 그룹의 가장 큰 하위 그룹의 합(인수)
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;
}
하지만 상기 코드가 충분한 테스트를 거치면 문제가 있을 것입니다.
예를 들어 모두 마이너스인 그룹을 처리할 수 없기 때문에 (실제로는 가장 큰 마이너스를 찾아야 한다) 당분간 좋은 방법을 생각하지 못하고 먼저 붙여서 집에 가서 업데이트를 한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나 추가문제 설명 정수 배열 digits으로 표시되는 큰 정수가 제공됩니다. 큰 정수에는 선행 0이 포함되어 있지 않습니다. 설명 題目 題目 理解 理解 理解 理解 考量 考量 簡單 是 進位 進位 進位 進位 進位 也 很 很 簡...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.