文档章节

1027. Longest Arithmetic Sequence

大兔崽子
 大兔崽子
发布于 05/07 14:37
字数 283
阅读 7
收藏 0

Problem

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).

Solution

Use brute force. Traverse the array A and use an assistant matrix “maxlen” to keep the length of every arithmetic subsequence, where maxlen[i][j] represents the length of arithmetic subsequence ended at A[i] with difference of j - 10000 (j - 10000 because the difference can be negative). In addition, a key function to calculate maxlen[i][j] is maxlen[i][A[i] - A[j] + 10000] = maxlen[j][A[i] - A[j] + 10000] + 1.

Code

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int **maxlen = new int* [A.size()];
        for (int i = 0; i < A.size(); i++)
        {
            maxlen[i] = new int [20001];
        }
        int max = 2;
        for (int i = 0; i < A.size(); i++)
        {
            for (int j = 0; j < 20001; j++)
            {
                maxlen[i][j] = 1;
            }
        }
        for (int i = 1; i < A.size(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                maxlen[i][A[i] - A[j] + 10000] = maxlen[j][A[i] - A[j] + 10000] + 1;
                if (max < maxlen[i][A[i] - A[j] + 10000])
                {
                    max = maxlen[i][A[i] - A[j] + 10000];
                }
            }
        }
        return max;
    }
};

502 Love u

© 著作权归作者所有

大兔崽子
粉丝 1
博文 27
码字总数 24376
作品 0
杭州
私信 提问
【DP】1027. 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 ......

牛奶芝麻
04/30
0
0
求解:编译器tiny+语法分析,一个语法不知道怎么推导

EBNF如下,但bfactor不知道怎么推导,选(bool-exp)还是(comparison-exp)? stmt-sequence -> statement { ; statement } statement -> if-stmt | repeat-stmt | assign-stmt | read-stmt......

xiangxw
2010/11/19
332
2
至少有三个数,任意两个之间的差值相等 Arithmetic Slices

问题: A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. For example, t......

叶枫啦啦
2018/01/03
9
0
【Leetcode】413. Arithmetic Slices

Description A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. For examp......

xiagnming
2018/07/31
0
0
[Leetcode] Binary Tree Longest Consecutive Sequence 二叉搜索树最长序列

Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starti......

ethannnli
09/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mysql备份还有这么多套路,还不了解下?

逻辑备份和物理备份 逻辑备份 逻辑备份用于备份数据库的结构(CREAET DATABASE、CREATE TABLE)和数据(INSERT),这种备份类型适合数据量小、跨SQL服务器、需要修改数据等场景。如mysqldump...

架构文摘
9分钟前
4
0
吊打面试官——秒杀系统设计

首先设计一个系统之前,我们需要先确认我们的业务场景是怎么样子的,我就带着大家一起假设一个场景好吧。 场景 我们现在要卖100件下面这个婴儿纸尿裤,然后我们根据以往这样秒杀活动的数据经...

java后端开发
14分钟前
2
0
高频电子电路电磁兼容的设计要点

电磁兼容的问题常发生于高频状态下,个别问题(电压跌落与瞬时中断等)除外。高频思维,总而言之,就是器件的特性、电路的特性,在高频情况下和常规中低频 状态下是不一样的,如果仍然按照普...

demyar
16分钟前
2
0
JDK 12 JVM 垃圾回收器 Shenandoah GC 的实践案例

https://www.infoq.cn/article/L4LU1J0VxXtA6ASeGYbV

perofu
25分钟前
3
0
Linux下的计划任务--cron

linux任务计划cron介绍 大部分系统管理工作都是通过定期自动执行某个脚本来完成的,Linux的cron就是用来定期执行脚本的。 Linux任务计划功能的操作都是通过crontab命令来完成的,常用的选项有...

爱米修啊
27分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部