Python에서 대상 배열을 형성하기 위해 하위 배열에서 최소 증분 수를 찾는 프로그램

<시간/>

양수 값을 가진 target이라는 배열이 있다고 가정합니다. 이제 모두 0인 동일한 크기의 배열 이니셜을 고려하십시오. 이 작업을 수행하는 경우 초기값에서 대상 배열을 생성하는 데 필요한 최소 작업 수를 찾아야 합니다. (이니셜에서 하위 배열을 선택하고 각 값을 1씩 증가시킵니다.)

따라서 입력이 target =[2,3,4,3,2]와 같으면 초기 배열이 [0,0,0,0,0]이기 때문에 출력은 4가 됩니다. 4를 1씩 증가시켜 배열이 [1,1,1,1,1]이 되도록 한 다음 인덱스 0에서 4까지 다시 선택하여 [2,2,2,2,2]로 만든 다음 다음에서 요소를 선택합니다. 인덱스 1에서 3까지 증가시켜 배열이 [2,3,3,3,2]가 되고 마지막으로 인덱스 2를 선택하여 target과 동일한 배열 [2,3,4,3,2]를 만듭니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

이전 번호 :=0
단계 :=0
대상의 각 val에 대해 수행
- steps :=steps + val - val이면 prev_num> prev_num이면 0
- prev_num :=val
반환 단계

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

def solve(target):
   prev_num = 0
   steps = 0
   for val in target:
      steps += val-prev_num if val > prev_num else 0
      prev_num = val
   return steps

target = [2,3,4,3,2]
print(solve(target))

입력

[2,3,4,3,2]