最大和雙音子數組  


難度級別 中烘焙
經常問 思科 戴爾 風箏 高盛 雜貨店 IBM PayU Quora的 雅虎
排列 動態編程

問題陳述  

An 排列 有n個整數給我們。 我們需要找到 最大和雙音子數組。 雙音子陣列只不過是其中元素以特定順序排列的子陣列。 這樣第一個元素按升序排列,然後按降序排列,所以像a,a + 1,a + 4,a + 7,a-9,a-11之類。 在這裡,常數只是一些隨機數,它們滿足強加於數組的條件。 因為這只是為了顯示其訂購方式。 

 

  

最大和雙音子數組

Size of array = 7

Array = {1 2 5 4 10 20 1}
25

說明:可能有兩個雙音陣列,一個子陣列為{1 2 5 4},另一個為{4 10 20 1}。 由於我們需要最大的和,因此我們選擇第二個子數組。 我們的答案是4 + 10 + 20 + 1 = 25。

 

Size of array = 4

Array = { 100 200 300 10}
610

說明:由於整個陣列都滿足我們的雙生子條件。 我們的答案是610。

 

最大和雙音子陣列問題的方法  

天真的方法

我們可以為子數組的左右邊界使用兩個指針。 修復子陣列後,我們檢查此序列是否為雙子序列。 如果這是一個雙子陣列,那麼我們求和並相應地更新我們的答案。 如果採用這種方法,則需要三個嵌套 循環 這肯定不是最好的方法。

高效方法

我們可以以線性時間複雜度解決這個問題。 如果我們創建兩個子數組 離開對, 這表示如果我們的峰值是當前元素,那麼我們可以向左移動多遠,並將該和存儲在左數組的第i個索引處。 我們可以朝左方向走,直到 arr [i-1] 對於左側方向上的所有元素都滿足。 同樣,我們為正確的子數組做。 現在,我們遍歷原始數組,找到如果我們的當前元素是雙音子數組的峰值,則可以得到的雙音子數組的最大和。 在每個索引處,我們都會不斷更新答案。

查找最大總和數位子數組的代碼  

C ++代碼

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


int main(){
    int testCases;cin>>testCases;
    while(testCases--){
    	int inputSize;cin>>inputSize;
    	long long int input[inputSize];
    	for(int i=0;i<inputSize;i++){
    		cin>>input[i];
        }
        
        long long int leftSum[inputSize], rightSum[inputSize];
        for(int i=0;i<inputSize;i++)
        	leftSum[i] = rightSum[i] = input[i];
        
        leftSum[0] = input[0];
        for(int i=1;i<inputSize;i++){
        	if(input[i-1] < input[i])
        		leftSum[i] += leftSum[i-1];
        }
        
        rightSum[inputSize-1] = input[inputSize-1];
        for(int i=inputSize-2;i>=0;i--){
        	if(input[i] > input[i+1])
        		rightSum[i] += rightSum[i+1];
        }
        
        long long int answer = LLONG_MIN;
        for(int i=0;i<inputSize;i++){
        	answer = max(answer, leftSum[i] + rightSum[i] - input[i]);
        }
        cout<<answer<<endl;
    }
    return 0;
}
2
5
1 2 5 3 10
5
10 50 10 90 10
13
110

 

也可以看看
矩陣鏈乘法

Java代碼

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        while(testCases-- > 0){
        	int inputSize = sc.nextInt();
        	long input[] = new long[inputSize];
        	for(int i=0;i<inputSize;i++){
        		input[i] = sc.nextInt();
            }
            
            long leftSum[] = new long[inputSize];
            long rightSum[] = new long[inputSize];
            for(int i=0;i<inputSize;i++) {
            	leftSum[i] = input[i];
            	rightSum[i] = input[i];
            }
            
            leftSum[0] = input[0];
            for(int i=1;i<inputSize;i++){
            	if(input[i-1] < input[i])
            		leftSum[i] += leftSum[i-1];
            }
            
            rightSum[inputSize-1] = input[inputSize-1];
            for(int i=inputSize-2;i>=0;i--){
            	if(input[i] > input[i+1])
            		rightSum[i] += rightSum[i+1];
            }
            
            long answer = Long.MIN_VALUE;
            for(int i=0;i<inputSize;i++){
            	answer = Math.max(answer, leftSum[i] + rightSum[i] - input[i]);
            }
            System.out.println(answer);
        }
    }
}
2 
5 
1 2 5 3 10 
5 
10 50 10 90 10
13
110

複雜度分析  

時間複雜度: 上)

因為我們遍歷數組一次或兩次,所以沒有嵌套循環。 我們有一個線性的時間複雜度。

空間複雜度: 上)

在這裡,我們製作了兩個臨時數組,大小分別為leftSum和rightSum = inputSize。 由於它們是一維數組,因此我們也具有線性空間複雜度。