2010-5-25 Maximum Sum
오늘은 좀 심심해서 주드 온라인으로 달려가서 문제를 풀었는데, 선택한 제목은 다음과 같다.
Maximum Sum
Time Limit: 15 Sec Memory Limit: 128 MB Submissions: 523 Solved: 41
Description
Given an integer array, how will you find out the increasing subsequence which gives the largest sum. For example, 4, 2, 1, 5, 3 in this subsequence a few possible increasing subsequences are 1) 4 2) 2 3) 1 4) 5 5) 3 6) 4, 5 7) 2, 5 8) 2, 3 9) 1, 5 10) 1, 3 but 4, 5 gievs the maximum sum. Your task is how to find such the maximum sum in a given integer array.
Input
Multiply Cases, For each case: The first line contains N(0< N <=1000000), which is the number of the integer array. The second line contains N integer numbers not exceeding 2000000 by the absolute value.
Output
For each case, output only one integer, which is the maximum sum of increasing subsequences.
Sample Input
5
4 2 1 5 3
Sample Output
9
， ， ， ， ， ， ：
#include <stdio.h>
#define N 1000000
int main(){
int n = 0, i = 0, j = 0;
int data[N], rec[N], tmp = 0, max, maxn;
scanf("%d", &n);
for(;i < n;i++){
scanf("%d", &data[i]);
rec[i] = data[i];
}
max = rec[0];
maxn = 0;
for(i = 1; i <n; i ++){
for(j = i -1 ; j >= 0; j --){
if(data[j] < data[i]){
if(j == maxn){
rec[i] = max + data[i];
max = rec[i];
maxn = i;
goto out;
}
else{
if((tmp = rec[j] + data[i]) > rec[i]){
rec[i] = tmp;
}
}
}
}
if(rec[i] > max){
max = rec[i];
maxn = i;
}
out: ;
}
printf("%d", max);
return 0;
}
， ！
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
