주어진 배열의 “최대 하위 배열”을 “가장 큰 합계를 갖는 (연속적인) 하위 배열”로 정의하십시오. “0이 아닌”요구 사항은 없습니다. 그 합계를 출력합니다.
가능하면 코드에 대한 설명을 제공하십시오.
샘플 입력 1 :
1 2 3 -4 -5 6 7 -8 9 10 -11 -12 -13 14
샘플 출력 1 : 24
설명 1 :
잘라 6 7 -8 9 10내고 합산하면 가장 큰 합계가 산출됩니다 .
샘플 입력 2 : -1 -2 -3
샘플 출력 2 : 0
설명 2 : 간단합니다. 빈 하위 배열이 “가장 큰”것입니다.
요구 사항 :
- stdin 이외의 것을 읽지 않으면 출력이 stdout으로 이동해야합니다.
- 표준 허점 제한이 적용됩니다.
순위 : 가장 짧은 프로그램이이 code-golf를 이깁니다 .
답변
껍질 , 6 4 바이트
▲ṁ∫ṫ
-- implicit input (list) xs - eg. [-1,2,3]
ṫ -- get all tails of xs - [[-1,2,3],[2,3],[3],[]]
ṁ∫ -- map & concat cumsum - [0,-1,1,4,0,2,5,0,3,0]
▲ -- get maximum - 5
답변
파이썬 3 , 61 바이트
a=b=0
for x in eval(input()):a=max(x,a+x);b=max(a,b)
print(b)Wikipedia 에서 도난당한 알고리즘 .
답변
Pyth , 8 바이트
eS+0sM.:
방법?
eS + 0sM. : Q-Q는 암시 적이며 입력을 의미합니다. 그것이 [-1, -2, -3]이라고 가정 해 봅시다.
. :-비어 있지 않은 모든 비 하위 서브리스트. [[-1], [-2], [-3], [-1, -2], [-2, -3], [-1, -2, -3]이 있습니다.
sM-각 하위 목록의 합계를 가져옵니다. [-1, -2, -3, -3, -5, -6]
+0-합계 목록에 0을 추가합니다. [0, -1, -2, -3, -3, -5, -6]
eS-최대 요소. S는 [-6, -5, -3, -3, -2, -1, 0]을, e는 마지막 요소 인 0을 반환합니다.
답변
답변
답변
C ++, 197 195 187 바이트
Zacharý 덕분에 -10 바이트
#include<vector>
#include<numeric>
int f(std::vector<int>v){int i=0,j,t,r=0;for(;i<v.size();++i)for(j=i;j<v.size();++j){t=std::accumulate(v.begin()+i,v.begin()+j,0);if(t>r)r=t;}return r;}답변
R , 54 바이트
a=b=0;for(x in scan()){a=max(x,a+x);b=max(a,b)};cat(b)알고리즘 : 최대 부분 배열 문제
R , 65 바이트
y=seq(x<-scan());m=0;for(i in y)for(j in y)m=max(m,sum(x[i:j]));mxstdin에서 읽습니다 .- 의
y색인으로 설정하십시오x. - 비어 있지 않은 모든 가능한 하위 집합을 두 번 반복합니다.
m(초기m=0) 와 부분 집합의 합계를 비교합니다 .- 최대 값을에 저장하십시오
m. - 의 값을 인쇄합니다
m.
R , 72 바이트
n=length(x<-scan());m=0;for(i in 1:n)for(j in i:n)m=max(m,sum(x[i:j]));mxstdin에서 읽습니다 .- 비어 있지 않은 모든 가능한 하위 집합에 대해 전체 검색을 수행하십시오.
m(초기m=0) 와 부분 집합의 합계를 비교합니다 .- 최대 값을에 저장하십시오
m. - 의 값을 인쇄합니다
m.
다른 실패한 아이디어
58 바이트
Reduce(max,lapply(lapply(seq(x<-scan()),tail,x=x),cumsum))63 바이트
Reduce(max,lapply(seq(x<-scan()),function(i)cumsum(tail(x,i))))72 바이트
m=matrix(x<-scan(),n<-length(x),n);max(apply(m*lower.tri(m,T),2,cumsum))