ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದ ಗರಿಷ್ಠ ಉತ್ಪನ್ನ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಕೋಲೈಟ್ ಜಿಇ ಹೆಲ್ತ್ಕೇರ್ ಹ್ಯಾಕರ್ರ್ಯಾಂಕ್ ಐಬಿಎಂ Snapchat ಯಾಹೂ
ಅರೇ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದ ಗರಿಷ್ಠ ಉತ್ಪನ್ನ” ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದ ಅಂಶಗಳನ್ನು ನೀವು ಗುಣಿಸಿದಾಗ ನೀವು ಸಾಧಿಸಬಹುದಾದ ಗರಿಷ್ಠ ಉತ್ಪನ್ನವನ್ನು ಈಗ ನೀವು ಕಂಡುಹಿಡಿಯಬೇಕು. ಗಮನಿಸಬೇಕಾದ ವಿಷಯವೆಂದರೆ, ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದದನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿಲ್ಲ. ನಾವು ಸಣ್ಣ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿರಬಹುದು ಆದರೆ ಅದು ಗರಿಷ್ಠ ಉತ್ಪನ್ನವನ್ನು ಹೊಂದಿರಬೇಕು.

ಉದಾಹರಣೆ

ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದ ಗರಿಷ್ಠ ಉತ್ಪನ್ನ

10, 1, 1000, 2, 3, 4
10000

ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದ ಗರಿಷ್ಠ ಉತ್ಪನ್ನ 10, 1000. ದೀರ್ಘಾವಧಿಯ ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದವು {1, 2, 3, 4 is ಆಗಿದ್ದರೂ ಸಹ.

ಅಪ್ರೋಚ್

ಸಮಸ್ಯೆ ಹೋಲುತ್ತದೆ ದೀರ್ಘಾವಧಿಯ ಹೆಚ್ಚುತ್ತಿರುವ ಪರಿಣಾಮ ಸಮಸ್ಯೆ. ಆ ಸಮಸ್ಯೆಯ ಮೇಲೆ ಸ್ವಲ್ಪ ಮಾರ್ಪಾಡು ಏನೆಂದರೆ, ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದದನ್ನು ಕಂಡುಹಿಡಿಯುವ ಬದಲು. ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದ ಗರಿಷ್ಠ ಉತ್ಪನ್ನವನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕು.

ಆದ್ದರಿಂದ, ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು. ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ನಾವು ಬ್ರೂಟ್ ಫೋರ್ಸ್ ಅಪ್ರೋಚ್ ಅನ್ನು ಬಳಸಬಹುದು. ಈ ವಿಧಾನವು ಅಸಮರ್ಥವಾಗಿದ್ದರೂ ಸಹ ತಿಳಿದಿರಬೇಕು. ಆದ್ದರಿಂದ, ವಿವೇಚನಾರಹಿತ ವಿಧಾನದಲ್ಲಿ, ನಾವು ಮೊದಲು ಎಲ್ಲಾ ನಂತರದವುಗಳನ್ನು ಉತ್ಪಾದಿಸುತ್ತೇವೆ. ನಂತರದವುಗಳನ್ನು ರಚಿಸಿದ ನಂತರ, ನಾವು ಚೆಕರ್ ಕಾರ್ಯವನ್ನು ರಚಿಸುತ್ತೇವೆ. ಚೆಕರ್ ಕಾರ್ಯದಲ್ಲಿ, ನಂತರದವು ಮಾನ್ಯವಾಗಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಚೆಕರ್ ಕಾರ್ಯದ ಸಿಂಧುತ್ವ ಎಂದರೆ ನಂತರದವು ಹೆಚ್ಚುತ್ತಿರುವ ಅನುಕ್ರಮವಾಗಿರಬೇಕು. ಅದರ ನಂತರ, ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದ ಉತ್ಪನ್ನದಿಂದ ನಾವು ಗರಿಷ್ಠ ಉತ್ಪನ್ನವನ್ನು ನವೀಕರಿಸುತ್ತಲೇ ಇರುತ್ತೇವೆ.

ಈಗ ನಾವು ಸಮಸ್ಯೆಯನ್ನು ಹೇಗೆ ಸಮರ್ಥವಾಗಿ ಪರಿಹರಿಸುತ್ತೇವೆ ಎಂಬುದು ಪ್ರಶ್ನೆ. ಸಮಸ್ಯೆಯನ್ನು ಸಮರ್ಥವಾಗಿ ಪರಿಹರಿಸಲು, ನಾವು ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಅನ್ನು ಬಳಸುತ್ತೇವೆ. ಸಮಸ್ಯೆಯಲ್ಲಿನ ಪರಿವರ್ತನೆಯು ಎಲ್ಐಎಸ್ ಸಮಸ್ಯೆಯಂತೆಯೇ ಇರುತ್ತದೆ. ಪ್ರಸ್ತುತ ಅಂಶದವರೆಗೆ ನಾವು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಪರಿಗಣಿಸಿದರೆ ಸಾಧಿಸಬಹುದಾದ ಗರಿಷ್ಠ ಉತ್ಪನ್ನವನ್ನು ನಮ್ಮ ಡಿಪಿ ರಚನೆಯು ಸಂಗ್ರಹಿಸುತ್ತದೆ. ಮತ್ತು ನಂತರದವು ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ಹೊಂದಿರಬೇಕು ಎಂಬ ಇನ್ನೊಂದು ಷರತ್ತು ಇದೆ. ನಂತರ ಡಿಪಿ ವ್ಯೂಹವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ನಾವು ನೆಸ್ಟೆಡ್ ಲೂಪ್ ಅನ್ನು ಪ್ರಸ್ತುತ ಅಂಶದಿಂದ ಆರಂಭಿಕ ಅಂಶಕ್ಕೆ ಹಿಂದುಳಿದ ದಿಕ್ಕಿನಲ್ಲಿ ಓಡಿಸುತ್ತೇವೆ. ಪ್ರಸ್ತುತ ಅಂಶಕ್ಕಿಂತ ಚಿಕ್ಕದಾದ ಒಂದು ಅಂಶವನ್ನು ನಾವು ಕಂಡುಕೊಂಡರೆ, ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ಡಿಪಿ ಶ್ರೇಣಿಯಲ್ಲಿನ ಆ ಸೂಚ್ಯಂಕದಲ್ಲಿನ ಅಂಶಕ್ಕೆ ಗುಣಿಸಿದಾಗ ಪ್ರಸ್ತುತ ಸಂಗ್ರಹವಾಗಿರುವ ಮೌಲ್ಯಕ್ಕಿಂತ ಹೆಚ್ಚಿದ್ದರೆ ನಾವು ನಮ್ಮ ಉತ್ತರವನ್ನು ನವೀಕರಿಸುತ್ತೇವೆ.

ಕೋಡ್

ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದ ಗರಿಷ್ಠ ಉತ್ಪನ್ನವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

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


int maxProductOfIncreasingSubsequence(vector<int> &input){
  vector<int> dp(n);
  dp[0] = input[0];
  int ans = input[0];
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(input[j] < input[i])
        dp[i] = max(dp[i], dp[j]*input[i]);
    }
    ans = max(ans, dp[i]);
  }
  return ans;
}

int main(){
  int n;cin>>n;
  vector<int> input(n);
  for(int i=0;i<n;i++)
    cin>>input[i];

  cout<<maxProductOfIncreasingSubsequence(input);
}
6
10 1 1000 2 3 4
10000

ಹೆಚ್ಚುತ್ತಿರುವ ನಂತರದ ಗರಿಷ್ಠ ಉತ್ಪನ್ನವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

import java.util.*;

class Main{
    static int maxProductOfIncreasingSubsequence(ArrayList<Integer> input){
    ArrayList<Integer> dp = new ArrayList<Integer>();
    dp.add(input.get(0));
    int ans = input.get(0);
    int n = input.size();
    for(int i=1;i<n;i++){
      dp.add(input.get(i));
      for(int j=0;j<i;j++){
        if(input.get(j) < input.get(i))
          dp.set(i, Math.max(dp.get(i), dp.get(j)*input.get(i)));
      }
      ans = Math.max(ans, dp.get(i));
    }
    return ans;
  }

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> input = new ArrayList<>();
    for(int i=0;i<n;i++){
      int in = sc.nextInt();
      input.add(in);
    }

    int answer = maxProductOfIncreasingSubsequence(input);
    System.out.print(answer);
  }
}
6
10 1 1000 2 3 4
10000

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

O (N ^ 2) ಏಕೆಂದರೆ ನಾವು ಎರಡು ನೆಸ್ಟೆಡ್ ಲೂಪ್‌ಗಳನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ. ಒಂದು ಎಲ್ಲಾ ಅಂಶಗಳ ಮೇಲೆ ಚಲಿಸುತ್ತದೆ ಮತ್ತು ಇನ್ನೊಂದು ಆಂತರಿಕ ಲೂಪ್ ಎಲ್ಲಾ ಅಂಶಗಳ ಮೇಲೆ ಪ್ರಸ್ತುತ ಅಂಶದವರೆಗೆ ಚಲಿಸುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್) ಏಕೆಂದರೆ ನಾವು ಏಕ ಆಯಾಮದ ಡಿಪಿ ಟೇಬಲ್ ಅನ್ನು ರಚಿಸುತ್ತೇವೆ. ಹೀಗಾಗಿ ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.