LeetCode 1027. Longest Arithmetic Sequence
原题链接在这里:https://leetcode.com/problems/longest-arithmetic-sequence/
题目:
Given an array A
of integers, return the length of the longest arithmetic subsequence in A
.
Recall that a subsequence of A
is a list A[i_1], A[i_2], ..., A[i_k]
with 0 <= i_1 < i_2 < ... < i_k <= A.length - 1
, and that a sequence B
is arithmetic if B[i+1] - B[i]
are all the same value (for 0 <= i < B.length - 1
).
Example 1:
Input: [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].
Note:
2 <= A.length <= 2000
0 <= A[i] <= 10000
题解:
State, let dp[diff][i] denotes with diff, up to index i, longest arithmetic length.
For j, check each i<j, with the same diff, dp[diff][j] = dp[diff][i]+1.
Time Complexity: O(n^2). n = A.length.
Space: O(n*(max-min)). max is largest value in A, min is minimum value in A. since count of distinct diff can't be more max-min.
AC Java:
class Solution {
public int longestArithSeqLength(int[] A) {
if(A == null || A.length == 0){
return 0;
} int n = A.length;
int res = 1;
HashMap<Integer, Integer> [] dp = new HashMap[n];
for(int j = 0; j<n; j++){
dp[j] = new HashMap<>();
for(int i = j-1; i>=0; i--){
int d = A[j] - A[i];
int cur = dp[j].getOrDefault(d, 1);
dp[j].put(d, Math.max(cur, dp[i].getOrDefault(d, 1)+1));
res = Math.max(res, dp[j].get(d));
}
} return res;
}
}
最新文章
- 折叠ListView
- java中Finally块的执行
- js删除所有子元素
- UVA 12950 : Even Obsession(最短路Dijkstra)
- OkHttp 详解
- C/C++中产生随机数
- <;转>;如何将Chrome变成开发利器,开发者们在用这些插件
- ASP.NET项目中使用CKEditor +CKFinder 实现上传图片
- C - Critical Links - uva 796(求桥)
- IPMITOOL常用操作指令
- 利用JS实现闪烁字体
- 是否使用安全模式启动word
- day13 闭包及装饰器
- python学习记录20190121
- struct,map,json 互相转换
- zabbix 应用监控作业笔记 ansible-playbook
- 导出数据之CSV
- Android 音视频深入 十一 FFmpeg和AudioTrack播放声音(附源码下载)
- 部门sonarque代码扫描测试服务器docker化
- BearSkill纯代码搭建iOS界面
热门文章
- 【leetcode-78 dfs+回溯】 子集
- Spring对于事务的控制@Transactional注解详解
- pandas-10 pd.pivot_table()透视表功能
- Bootstrap-实现简单的网站首页
- AudioToolbox--利用AudioQueue音频队列,通过缓存对声音进行采集与播放
- 实战AudioToolbox--在iOS平台上播放音频
- MySQL分组查询每组最新的一条数据(通俗易懂)
- Jenkins详细教程
- linux上安装redis-单机版
- JS基础 浏览器弹出的三种提示框(提示信息框、确认框、输入文本框)