current position:Home>leetcode 1043. Partition Array for Maximum Sum (python)
leetcode 1043. Partition Array for Maximum Sum (python)
2022-01-31 21:42:08 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 19 God , Check out the activity details :2021 One last more challenge 」
describe
Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.
Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]
Copy code
Example 2:
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
Copy code
Example 3:
Input: arr = [1], k = 1
Output: 1
Copy code
Note:
1 <= arr.length <= 500
0 <= arr[i] <= 10^9
1 <= k <= arr.length
Copy code
analysis
According to the meaning , Given an array of integers arr, Divide the array into several, with a length of at most k A continuous subarray of . After partition , The value of each subarray becomes the maximum value of the subarray . The title requires us to return the maximum possible sum of the new array after partitioning . The meaning of the question is very clear , Combined with example 1, we can fully understand the meaning of the question .
This question was written after reading the answer of the great God , Using a one-dimensional dynamic programming array solution , There is a link at the end of the text
- The initialization length is len(arr) One dimensional array of , dp[i] That means arr[:i] The maximum sum obtained after operation ,
- Traverse range(N) , That's traversal arr All element position indexes in i , Re traversal range(i,max(-1, i-k),-1) That is, the possible subarray location index j , Constantly update the maximum value of the current sub array MAX, And constantly updated dp[i] = max(dp[i], dp[j-1] + MAX*(i-j+1)) , Pay attention to the limitations of boundary conditions .
- Return after traversal dp[-1] Is the answer
answer
class Solution(object):
def maxSumAfterPartitioning(self, arr, k):
"""
:type arr: List[int]
:type k: int
:rtype: int
"""
N = len(arr)
dp = [0 for _ in range(N)]
for i in range(N):
MAX = 0
for j in range(i,max(-1, i-k),-1):
MAX = max(arr[j], MAX)
if j>=1:
dp[i] = max(dp[i], dp[j-1] + MAX*(i-j+1))
else:
dp[i] = max(dp[i], MAX*(i-j+1))
return dp[-1]
Copy code
Running results
Runtime: 408 ms, faster than 61.04% of Python online submissions for Partition Array for Maximum Sum.
Memory Usage: 13.4 MB, less than 94.81% of Python online submissions for Partition Array for Maximum Sum.
Copy code
Original link :leetcode.com/problems/pa…
Explanation of the great God :www.bilibili.com/video/BV143…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201312142064046.html
The sidebar is recommended
- Python crawls the map of Gaode and the weather conditions of each city
- leetcode 1275. Find Winner on a Tic Tac Toe Game(python)
- leetcode 2016. Maximum Difference Between Increasing Elements(python)
- Run through Python date and time processing (Part 2)
- Application of urllib package in Python
- Django API Version (II)
- Python utility module playsound
- Database addition, deletion, modification and query of Python Sqlalchemy basic operation
- Tiobe November programming language ranking: Python surpasses C language to become the first! PHP is about to fall out of the top ten?
- Learn how to use opencv and python to realize face recognition!
guess what you like
-
Using OpenCV and python to identify credit card numbers
-
Principle of Python Apriori algorithm (11)
-
Python AI steals your voice in 5 seconds
-
A glance at Python's file processing (Part 1)
-
Python cloud cat
-
Python crawler actual combat, pyecharts module, python data analysis tells you which goods are popular on free fish~
-
Using pandas to implement SQL group_ concat
-
How IOS developers learn Python Programming 8 - set type 3
-
windows10+apache2. 4 + Django deployment
-
Django parser
Random recommended
- leetcode 1560. Most Visited Sector in a Circular Track(python)
- leetcode 1995. Count Special Quadruplets(python)
- How to program based on interfaces using Python
- leetcode 1286. Iterator for Combination(python)
- leetcode 1418. Display Table of Food Orders in a Restaurant (python)
- Python Matplotlib drawing histogram
- Python development foundation summary (VII) database + FTP + character coding + source code security
- Python modular package management and import mechanism
- Django serialization (II)
- Python dataloader error "dataloader worker (PID XXX) is killed by signal" solution
- apache2. 4 + Django + windows 10 Automated Deployment
- leetcode 1222. Queens That Can Attack the King(python)
- leetcode 1387. Sort Integers by The Power Value (python)
- Tiger sniffing 24-hour praise device, a case with a crawler skill, python crawler lesson 7-9
- Python object oriented programming 01: introduction classes and objects
- Baidu Post: high definition Python
- Python Matplotlib drawing contour map
- Python crawler actual combat, requests module, python realizes IMDB movie top data visualization
- Python classic: explain programming and development from simple to deep and step by step
- Python implements URL availability monitoring and instant push
- Python avatar animation, come and generate your own animation avatar
- leetcode 1884. Egg Drop With 2 Eggs and N Floors(python)
- leetcode 1910. Remove All Occurrences of a Substring(python)
- Python and binary
- First acquaintance with Python class
- [Python data collection] scrapy book acquisition and coding analysis
- Python crawler from introduction to mastery (IV) extracting information from web pages
- Python crawler from entry to mastery (III) implementation of simple crawler
- The apscheduler module in Python implements scheduled tasks
- 1379. Find the same node in the cloned binary tree (Java / C + + / Python)
- Python connects redis, singleton and thread pool, and resolves problems encountered
- Python from 0 to 1 (day 11) - Python data application 1
- Python bisect module
- Python + OpenGL realizes real-time interactive writing on blocks with B-spline curves
- Use the properties of Python VTK implicit functions to select and cut data
- Learn these 10000 passages and become a humorous person in the IT workplace. Python crawler lessons 8-9
- leetcode 986. Interval List Intersections(python)
- leetcode 1860. Incremental Memory Leak(python)
- How to teach yourself Python? How long will it take?
- Python Matplotlib drawing pie chart