최대 하위 배열 배열”을 “가장 큰 합계를

주어진 배열의 “최대 하위 배열”을 “가장 큰 합계를 갖는 (연속적인) 하위 배열”로 정의하십시오. “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으로 이동해야합니다.
  • 표준 허점 제한이 적용됩니다.

순위 : 가장 짧은 프로그램이이 이깁니다 .



답변

껍질 , 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을 반환합니다.

답변

05AB1E , 4 바이트

Ό0M

온라인으로 사용해보십시오!

Adnan 에게 -1 감사합니다 .


답변

젤리 , 6 바이트

ẆS€;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]));m

온라인으로 사용해보십시오!

  • xstdin에서 읽습니다 .
  • 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]));m

온라인으로 사용해보십시오!

  • xstdin에서 읽습니다 .
  • 비어 있지 않은 모든 가능한 하위 집합에 대해 전체 검색을 수행하십시오.
  • 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))