matlab求矩阵列最大值_双音阵列的最大值

偏执的太偏执、 2023-03-05 12:43 20阅读 0赞

matlab求矩阵列最大值

**Problem statement:**

**问题陈述：**

**Given a bitonic array find the maximum value of the array**. An array is said to be **bitonic** if it has an increasing sequence of integers followed immediately by a decreasing sequence of integers.

**给定一个双音阵列，找到该阵列的最大值** 。 如果数组具有递增的整数序列，紧随其后的是递减的整数序列，则称其为**双偶数** 。

**Example:**

**例：**

Input:
    1 4 8 3 2
    
    Output:
    8

**Solution:**

**解：**

Definitely the brute force solution even works in linear time where you just pick each element and compare with the previous & next element. That’s pretty simple. But the concept of [bitonic search][] leads up to more optimized solution reducing the number of comparison.

绝对可以说，蛮力解决方案甚至可以在线性时间内工作，您只需选择每个元素并与上一个和下一个元素进行比较即可。 那很简单。 但是[双音搜索][bitonic search]的概念导致了更优化的解决方案，从而减少了比较次数。

**Algorithm:**

**算法：**

**Pre-requisite:**

**先决条件：**

Bitonic array, low index (lower bound), high index (upper bound)

Bitonic数组， 低索引(低界)， 高索引(高界)

FUNCTION findMaxBitonic (Input array, low, high){
        While(low<=high){
            1.	Set mid to (low+high)/2;
            2.	Comparisons
            IF(array [mid]>array[mid-1] &&array[mid]>array[mid+1])
                Return array[mid]; //as this is the maximum
            //in the increasing region of the bitonic array
            IF(array[mid]>array[mid-1] &&array[mid]<array[mid+1]) 
                low=mid+1; //move lower bound up
            //in the decreasing region of the bitonic array
            ELSE IF(array[mid]<array[mid-1] &&array[mid+1]<array[mid])
                high=mid-1; //move upper bound down
        END WHILE
        IF control comes out of the loop
            //for trivial cases like array size 1 or 2
            return array[array size-1]; 
    END FUNCTION

**Time complexity: O(log(n))**

**时间复杂度：O(log(n))**

**C++ implementation**

**C ++实现**

#include <bits/stdc++.h>
    using namespace std;
    
    //printing the array
    void print(vector<int> a,int n){
        
    	for(int i=0;i<n;i++)
    		cout<<a[i]<<" ";
    	cout<<endl;
    }
    
    
    //function to find the max
    int findMaxBitonic(vector<int> a,int low,int high){
         
    	while(low<=high){
        
    		int mid=(low+high)/2;
    
    		if(a[mid]>a[mid-1] && a[mid]>a[mid+1]) //the maximum
    			return a[mid];
    		if(a[mid]>a[mid-1] && a[mid]<a[mid+1]) //in increasing zone
    			low=mid+1;
    		if(a[mid]<a[mid-1] && a[mid+1]<a[mid]) //in decreasing zone
    			high=mid-1;
    	}
    	return a[a.size()-1];
    }
    
    int main(){
        
    	int n,item;
    
    	cout<<"enter array size: ";
    	scanf("%d",&n);
    
    	vector<int> a;
    
    	cout<<"input bitonic array of size: "<<n<<endl;
    	for(int j=0;j<n;j++){
        
    		scanf("%d",&item);
    		a.push_back(item);
    	}
    	cout<<"your bitonic array is:\n";
    	print(a,n);
    	cout<<"maximum in this bitonic array is:"<<findMaxBitonic(a,0,n-1)<<endl;
    	
    	return 0;
    }

**Output**

**输出量**

First run:
    enter array size: 5
    input bitonic array of size: 5
    1 4 8 3 2
    your bitonic array is:
    1 4 8 3 2
    maximum in this bitonic array is:8
    
    Second run:
    enter array size: 10
    input bitonic array of size: 10
    6 8 20 12 11 9 7 5 0 -4
    your bitonic array is:
    6 8 20 12 11 9 7 5 0 -4
    maximum in this bitonic array is:20

**Explanation with example:**

**举例说明：**

Input array, arr:
    1 4 8 3 2
    Array size: 5
    
    In the main function we call findMaxBitonic (arr, 0, 4);
    Input array = arr
    low = 0
    high = 4
    -----------------------------------------------------------
    
    findMaxBitonic (arr, 0, 4)
    0th iteration
    low<high (0<4)
    mid= (low +high)/2 = 2
    arr[mid]>arr[mid+1] && arr[mid]>arr[mid-1] // 8>4 && 8>3
    return arr[mid] //return 8
    maximum in the bitonic array=8

So, in this input case we only need one comparison, where if we had done in brute force, would have required 3 comparisons.

因此，在这种情况下，我们只需要进行一次比较，而如果我们用蛮力完成，则需要进行3次比较。

> 翻译自: [https://www.includehelp.com/icp/maximum-value-in-a-bitonic-array.aspx][https_www.includehelp.com_icp_maximum-value-in-a-bitonic-array.aspx]

matlab求矩阵列最大值

[bitonic search]: https://www.includehelp.com/algorithms/bitonic-search.aspx
[https_www.includehelp.com_icp_maximum-value-in-a-bitonic-array.aspx]: https://www.includehelp.com/icp/maximum-value-in-a-bitonic-array.aspx