我和乘子交替方向法admm

Problem statement:

問題陳述：

Given a sequence of numbers, you have to find the maximum sum alternating subsequence and print the value. A sequence is an alternating sequence when it will be maintain like (increasing) -> (decreasing) ->(increasing) ->(decreasing).

給定一個數字序列，您必須找到最大和交替子序列并打印值 。 當序列將像(增加)->(減少)->(增加)->(減少)一樣被維護時，它是一個交替的序列。

Input:
T Test case
T no. of input string will be given to you.
E.g.
3
2 3 4 8 2 5 6 8
2 3 4 8 2 6 5 4
6 5 9 2 10 77 5
Constrain:
1≤ A[i] ≤50
Output:
Print the value of maximum sum alternating subsequence.

Example

例

T=3
Input:
2 3 4 8 2 5 6 8 
Output:
22 ( 8+6+8)
Input:
2 3 4 8 2 6 5 4
Output:
20 ( 8+ 2+ 6+ 4)
Input:
6 5 9 2 10 77 5
Output:
98 (5+ 9+ 2+ 77+5)

Explanation with example:

舉例說明：

Let N be the number of elements say, X1, X2, X3, ..., Xn

令N為元素的數量，即X1，X2，X3，...，Xn

Let f(a) = the value at the index a of the increasing array, and g(a) = the value at the index a of the decreasing array.

令f(a) =遞增數組的索引a處的值， g(a) =遞減數組的索引a處的值。

To find out the maximum sum alternating sequence we will follow these steps,

為了找出最大和交替序列，我們將按照以下步驟操作，

1. We take two new arrays, one is increasing array and another is decreasing array and initialize it with 0. We start our algorithm with the second column. We check elements that are before the current element, with the current element.

   我們采用兩個新數組，一個是遞增數組，另一個是遞減數組，并將其初始化為0。我們從第二列開始我們的算法。 我們使用當前元素檢查當前元素之前的元素。

2. If any element is less than the current element then,

   如果任何元素小于當前元素，

   f(indexofthecurrentelement) = max?

   f(當前元素的索引)=max?

3. If the element is greater than the current element then,

   如果元素大于當前元素，

   g(indexofthecurrentelement) = max?

   g(當前元素的索引)=max?

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
int sum(int* arr, int n)
{
int inc[n + 1], dec[n + 1];
inc[0] = arr[0];
dec[0] = arr[0];
memset(inc, 0, sizeof(inc));
memset(dec, 0, sizeof(dec));
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i]) {
dec[i] = max(dec[i], inc[j] + arr[i]);
}
else if (arr[i] > arr[j]) {
inc[i] = max(inc[i], dec[j] + arr[i]);
}
}
}
return max(inc[n - 1], dec[n - 1]);
}
int main()
{
int t;
cout << "Test Case : ";
cin >> t;
while (t--) {
int n;
cout << "Number of element : ";
cin >> n;
int arr[n];
cout << "Enter the elements : ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Sum of the alternating sequence : " << sum(arr, n) << endl;
}
return 0;
}

Output

輸出量

Test Case : 3
Number of element : 8
Enter the elements : 2 3 4 8 2 5 6 8
Sum of the alternating sequence : 22
Number of element : 8              
Enter the elements : 2 3 4 8 2 6 5 4
Sum of the alternating sequence : 20
Number of element : 7
Enter the elements : 6 5 9 2 10 77 5
Sum of the alternating sequence : 98

翻譯自: https://www.includehelp.com/icp/find-the-maximum-sum-alternating-subsequence.aspx

我和乘子交替方向法admm