Save Your Life (Kadane's Algorith)

PHOTO EMBED

Sat May 20 2023 10:32:07 GMT+0000 (Coordinated Universal Time)

Saved by @Ranjan_kumar #c++

class Solution{
public:
      string maxSum(string w,char x[], int b[],int n){
          // code here        
          unordered_map<char,int> mp;
          for(int i=0;i<w.size();i++)
          {
              mp[w[i]]=int(w[i]);
          }
          for(int i=0;i<n;i++)
          {
              mp[x[i]]=b[i];
          }
          vector<int> v(w.size());
          for(int i=0;i<w.size();i++)
          {
              v[i]=mp[w[i]];
          }
          
          int edx=0, mxl=0, mxg=INT_MIN;
          for(int i=0;i<w.size();i++)
          {
              mxl=max(v[i], v[i]+mxl);
              
              if(mxl>mxg)
              {
                  mxg=mxl;
                  edx=i;
              }
          }
          int sdx=edx;
          while(sdx>=0)
          {
              mxg-=v[sdx];
              if(mxg==0) break;
              if(sdx==0) break;
              sdx--;
          }
          
          
          string ans="";
          for(int i=sdx;i<=edx;i++)
          {
              ans+=w[i];
          }
          return ans;
      }
};
content_copyCOPY

Kadane's Algorithms

https://practice.geeksforgeeks.org/problems/save-your-life4601/1?utm_source=gfg&utm_medium=article&utm_campaign=bottom_sticky_on_article