# 最大子序列总和，以使三个子序列都不连续

## 使用案列

a[] = {2, 5, 10}
50

a[] = {5, 10, 5, 10, 15}
40

## 代码

### C ++代码查找最大子序列和，以使三个子序列都不连续

#include <bits/stdc++.h>
using namespace std;

int main()
{
int a[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(a) / sizeof(a[0]);
int dp[n];

// base case
if(n>=0)dp[0] = a[0];
if(n>0)dp[1] = a[0] + a[1];
if(n>1)dp[2] = max({a[0] + a[1], a[2]+a[0], a[2]+a[1]});
// if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
// if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
// if you do not choose a[i], dp[i] = dp[i-1]
for (int i = 3; i < n; i++)
dp[i] = max({a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i], dp[i-1]});
cout<<dp[n-1];
}
16

### Java代码查找最大子序列和，以使三个子序列都不连续

import java.util.*;
class Main{
public static void main(String[] args)
{
int a[] = {1, 2, 3, 4, 5, 6};
int n = a.length;
int dp[] = new int[n];

// base case
if(n>=0)dp[0] = a[0];
if(n>0)dp[1] = a[0] + a[1];
if(n>1)dp[2] = Math.max(Math.max(a[0] + a[1], a[2]+a[0]), a[2]+a[1]);
// if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
// if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
// if you do not choose a[i], dp[i] = dp[i-1]
for (int i = 3; i < n; i++)
dp[i] = Math.max(Math.max(a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i]), dp[i-1]);

System.out.println(dp[n-1]);
}
}
16