算法

采用double linked list，双向链表。光标指向的地方就是当前结点，另外用一个vector存之前的最大前缀和。
每次左移就移动到prev，右移就next，同时更新vector。插入，删除操作同理。

时间复杂度

每次操作O（1）

[java] 代码

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
class Node {
    int val;
    int preSum;
    int maxSum;
    Node prev;
    Node next;
    public Node(int v, int pS, int mS, Node p, Node n) {
        val = v;
        preSum = pS;
        maxSum = mS;
        prev = p;
        next = n;
    }
}
public class Main {
    private static Node cur = new Node(0, 0, Integer.MIN_VALUE, null, null);;
    private static List<Node> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int Q = in.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < Q; ++i) {
            String op = in.next();
            if (op.equals("I")) {
                insert(in.nextInt());
            } else if (op.equals("L")) {
                moveLeft();
            } else if (op.equals("R")) {
                moveRight();
            } else if (op.equals("D")) {
                delete();
            } else if (op.equals("Q")) {
                sb.append(query(in.nextInt()));
                sb.append("\n");
            }
        }                
        in.close();
        System.out.print(sb);
    }

    private static void insert(int a) {
        cur.next = new Node(a, cur.preSum + a, Math.max(cur.maxSum, cur.preSum + a), cur, cur.next);
        cur = cur.next;
        list.add(cur);
    }

    private static void moveLeft() {
        if (cur.prev != null) {
            cur = cur.prev;
            list.remove(list.size() - 1);
        }
    }

    private static void moveRight() {
        if (cur.next != null) {
            cur.next.prev = cur;
            cur = cur.next;
            cur.preSum = cur.prev.preSum + cur.val;
            cur.maxSum = Math.max(cur.preSum, cur.prev.maxSum);
            list.add(cur);
        }
    }

    private static int query(int i) {
        return list.get(i - 1).maxSum;
    }

    private static void delete() {
        if (cur.prev != null) {
            Node temp = cur.prev;
            if (cur.next != null) cur.next.prev = cur.prev;
            cur.prev.next = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = temp;
            list.remove(list.size() - 1);
        }
    }
}