LeetCode--689_Maximum_Sum_of_3_NonOverlapping_Subarrays
2024-10-19 00:24:09
原题链接:点击这里
一道很水很水的背包问题? 大概算不上背包吧QAQ 自己的dp 真的是太差劲啦,以后每天一道LeetCode 备战秋招!
package leetcode; public class a689_Maximum_Sum_of_3_NonOverlapping_Subarrays { public static int[] maxSumOfThreeSubarrays(int[] nums, int k) { int [] ans = new int [3]; int [][] dp = new int [3][nums.length+1]; int [] sum = new int [nums.length+1]; for(int j=1;j<=nums.length;j++) { if(j==1) { sum[j]=nums[j-1]; }else { sum[j]+=sum[j-1]+nums[j-1]; } } int mmx =0; for(int j=0;j<3;j++) { int max = 0; for(int i = k*j+1;i<=nums.length-k+1;i++) { if(j==0) { dp[0][i] = sum[i+k-1]-sum[i-1]; }else { max = Math.max(max, dp[j-1][i-k]); dp[j][i] = max+sum[i+k-1]-sum[i-1]; mmx = Math.max(mmx, dp[j][i]); } } } for(int j=2;j>=0;j--) { for(int i=1;i<=nums.length-k+1;i++) { if(dp[j][i]==mmx) { ans[j]=i-1; mmx -= sum[i+k-1]-sum[i-1]; break; } } } return ans; } public static void main(String[] args) { int [] nums = {1,2,1,2,6,7,5,1}; int k = 2; maxSumOfThreeSubarrays(nums,k); } }
Runtime: 4 ms, faster than 82.08% of Java online submissions for Maximum Sum of 3 Non-Overlapping Subarrays.
Memory Usage: 42.6 MB, less than 34.91% of Java online submissions forMaximum Sum of 3 Non-Overlapping Subarrays.
最新文章
- Git 简介
- C语言程序设计第二次作业
- web前端职业规划(转)
- Linux读写锁的使用
- jquery工具函数browser() 辨别浏览器
- 《STL源代码剖析》---stl_alloc.h阅读笔记
- 图的BFS代码
- target-action传值
- 关于在eclipse上部署Tomcat时出现8080等端口被占用问题的解决方法
- VUE中总的逻辑关系和移动端mint-ui的应用接触
- Oracle中hex和raw的相互转换
- R语言查看栅格值
- DFA算法实现关键字查找(正则原理入门)
- Springboot helloworld入门最经典例子
- CentOS7配置FTP服务器增强版~(零基础学会FTP配置)
- Linux常用指令笔记
- Scrapy、Scrapy-redis组件
- 洛谷 P1181数列分段SectionI 【贪心】
- 【Linux】-NO.7.Linux.3.Maven.1.001-【CentOS 7 Install Maven 3.5】-
- iOS 新浪微博-4.0 OAuth授权