Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python을 사용하여 최대 오름차순 하위 배열 합계를 찾는 프로그램

<시간/>

nums라고 하는 양수 값의 배열이 있다고 가정하고 nums에서 오름차순 하위 배열의 가능한 최대 합을 찾아야 합니다. 하위 배열 [nums_l, nums_l+1, ..., nums_r-1, nums_r]은 모든 i에 대해 l <=i

따라서 입력이 nums =[15,25,35,5,15,55]와 같으면 [5,15,55]가 최대 합으로 하위 배열을 증가시키므로 출력은 75가 됩니다.

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

  • 총계:=숫자[0]

  • max_total:=nums[0]

  • 범위 1에서 숫자 크기까지의 i에 대해

    • nums[i]> nums[i-1]이면

      • 총계 :=총계 + 숫자[i]

    • 그렇지 않으면

      • 총계:=숫자[i]

    • total> max_total이면

      • max_total:=총계

  • 반환 max_total

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

def solve(nums):
   total=nums[0]
   max_total=nums[0]
   for i in range(1,len(nums)):
      if nums[i] > nums[i-1]:
         total+=nums[i]
      else:
         total=nums[i]
      if total > max_total:
         max_total=total
   return max_total
nums = [15,25,35,5,15,55]
print(solve(nums))

입력

[15,25,35,5,15,55]

출력

75